Proof of Convergence: Babylonian Method $x_{n+1}=\frac{1}{2}(x_n + \frac{a}{x_n})$ a) Let $a>0$ and the sequence $x_n$ fulfills $x_1>0$ and $x_{n+1}=\frac{1}{2}(x_n + \frac{a}{x_n})$ for $n \in \mathbb N$. Show that $x_n \rightarrow \sqrt a$ when $n\rightarrow \infty$.
I have done it in two ways, but I guess I'm not allowed to use the first one and the second one is incomplete. Can someone please help me?

*

*We already know $x_n \rightarrow \sqrt a$, so we do another step of the iteration and see that $x_{n+1} = \sqrt a$.


*Using limit, $x_n \rightarrow x, x_{n+1} \rightarrow x$ (this is the part I think it's incomplete, don't I have to show $x_{n+1} \rightarrow x$, how?), we have that
$$x = \frac x 2 (1 + \frac a {x^2}) \Rightarrow 1 = a/x^2 \Rightarrow x = \sqrt a$$
b) Let the sequence $x_n$ be defined as $x_{n+1}= 1 + \frac 1 {x_n} (n \in \mathbb N), x_1=1$. Show that it converges and calculate its limit.
"Tip: Show that sequences $x_{2n}$ and $x_{2n+1}$ monotone convergent to the limit."
I didn't understand the tip, how can this help me? Does it make a difference if the number is odd or even?
Thanks in advance!

For b):
Consider the function,
$F(x) = 1 + 1/x$.
If you set $F(x)$ to the identity function $x$ and solve for $x$ using the quadratic formula, you will see that $F(x)$ has two fixed points, one positive and one negative.
With a little thought you might guess that our sequence is converging to the positive fixed point,
$\alpha=\frac{1+\sqrt5}{2}$.
Notice that we can restrict the domain of $F(x)$ and analyze the decreasing function
$F: [1.5,\,  2] \to [1.5,\,  2]$
Let $u$ and $v$ be any two distinct points in the closed interval $[1.5,\,  2]$.
Then
$\frac{(F(v) - F(u))}{(v - u)}$
is equal to (algebra)
$\frac {-1}{uv}$
The absolute value of this number can be no larger than
$\frac {1}{1.5*1.5}$, which is equal to $\frac {4}{9}$.
Applying the Banach Fixed Point Theorem,
we see that our sequence $x_{n+1}= 1 + \frac 1 {x_n} (n \in \mathbb N^*), x_1=1$ converges to $\alpha$, since $F(x_1)$ is 2.
Addendum
Actually, for our situation, we don't have to use Banach's theorem. One can easily prove the following, which can also be used to prove convergence of our sequence $x_1, x_2, x_3, ...,$.
Proposition: Let $f(x)$ be a continuous strictly monotonic function mapping a closed interval
$I = [a,\, b]$
into itself.
Assume that there is exactly one fixed point $c$ for $f$ with $a < c < b$.
Then for all $n > 0$, $f^n(I)$ is a closed interval that contains $c$, with $c$ not an endpoint.
Suppose also there is positive $\lambda < 1$, such that for any $\alpha$ $\beta$ with $a < \alpha < \beta < b$, the absolute value of
$\frac{(f(\beta) - f(\alpha))}{(\beta - \alpha)}$
is less than $\lambda$.
Then the intersection, $\cap \, f^n(I) \, | \, n > 0$, contains only one point, $c$.
