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!
 A: For a) a simple proof exists and can be generalized to the sequence 
$$K x_{n+1}  = (K-1)x_n + \frac{a}{x_n^{K-1}}$$
which converges to $\sqrt[K]{a}$ (your sequence has $K=2$).
Use $\text{AM} \ge \text{GM}$ to show that
$x_{n+1} \ge \sqrt{a}$.
Now
$x_{n+1} - x_n = \frac{a - x_n^2}{2x_n} \le 0$ as $x_n \ge \sqrt{a}$ for $n \gt 1$.
Thus the sequence is monotonically decreasing (starting from $n=2$) and bounded below and so converges.
For b) refer to various proofs here: Why does this process, when iterated, tend towards a certain number? (the golden ratio?)
(The link above applies to $y_n = \frac{1}{x_n}$).
A: AM-GM inequality tells us, $$x_{n+1}=\frac{1}{2}\left(x_n+\dfrac{a}{x_n}\right) \ge \sqrt{x_n.\frac{a}{x_n}}=\sqrt{a}.$$ In other words, $\{x_2, x_3, x_4, \cdots\}$ is bounded below by $\sqrt{a}.$
Also, this implies that $$x_{n+1}-x_{n+2}=x_{n+1}-\dfrac12\left(x_{n+1}+\dfrac{a}{x_{n+1}}\right)=\dfrac{x_{n+1}^2-a}{2x_{n+1}}\ge0.$$ Therefore $x_2\ge x_3\ge x_4\ge\cdots.$
By the Monotone Convergent Theorem $\lim_{n \to \infty}x_n=l$ is exist as a real number and $$l=\dfrac12\left(l+\dfrac{a}{l}\right).$$
A: (a) Yes, you need to show first that $\langle x_n\rangle_n$ is convergent; once you know that, your argument shows that its limit must be $\sqrt a$. You might want to look first at the discussion below for (b).
(b) Yes, it does make a difference whether $n$ is odd or even. Calculate the first few values: $$x_1=1, x_2 = 2,x_3=\frac32,x_4=\frac53,x_5=\frac85,x_6=\frac{13}8.$$ Note that the sequence is oscillating: the odd-numbered terms are low, and the even-numbered terms are high. On the other hand, $x_1<x_3<x_5$, and $x_2>x_4>x_6$. This suggests that the sequence does converge to some limit $x$ in such a way that $$x_1<x_3<x_5<\dots <x<\dots<x_6<x_4<x_2\;.$$ 
If you can show that $x_{2n+1}<x_{2n+3}<x_2$ for all $n\ge 0$, you’ll know that the sequence of odd-numbered is monotone increasing and bounded above, which implies that it converges to some $x_{\text{odd}}$. Similarly, if you can show that $x_1<x_{2n+2}<x_{2n}$ for every $n\ge 1$, you’ll know that the sequence of even-numbered terms is monotone decreasing and bounded below, which implies that it converges to some $x_{\text{even}}$. Then you’ll have to find a way to show that $x_{\text{odd}}=x_{\text{even}}$.
(By the way, the terms of this sequence are the ratios of consecutive Fibonacci numbers, and their limit is $\varphi = \frac12(1+\sqrt 5)$.)
Added: After some algebra we get $$x_{n+2}=1+\frac1{x_{n+1}}=1+\left(1+\frac1{x_n}\right)^{-1}=\frac{2x_n+1}{x_n+1}$$ and $$x_{n+4}=\frac{5x_n+3}{3x_n+2}\;.$$ Thus, 
$$\begin{align*}
x_{n+4}<x_{n+2}&\text{ iff } \frac{5x_n+3}{3x_n+2}<\frac{2x_n+1}{x_n+1}\\
&\text{ iff }5x_n^2+8x_n+3<6x_n^2+7x_n+2\\
&\text{ iff }0<x_n^2-x_n-1\\
&\text{ iff }2x_n+1<x_n^2+x_n\\
&\text{ iff }x_{n+2}<x_n
\end{align*}\tag{1}$$
Since $x_4=\frac53<2=x_2$, it follows by induction from $(1)$ that $\langle x_{2n}:n\in\mathbb{Z}^+\rangle$ is a decreasing sequence. The calculation in $(1)$ remains valid if all of the inequalities are turned around, and $x_3=\frac32>1=x_1$, so essentially the same induction shows that $\langle x_{2n-1}:n\in\mathbb{Z}^+\rangle$ is a decreasing sequence.
Now let $\varphi=\frac12(1+\sqrt 5)$, the positive zero of $x^2-x-1$. Note that if $x$ is a positive real number, $x>\varphi$ iff $x^2-x-1>0$. Moreover,
$$\begin{align*}
x_{n+2}^2-x_{n+2}-1&=\left(\frac{2x_n+1}{x_n+1}\right)^2-\frac{2x_n+1}{x_n+1}-1\\
&=\frac{x_n^2-x_n-1}{(x_n+1)^2}\;,
\end{align*}$$
and $(x_n+1)^2>0$, so $x_{n+2}^2-x_{n+2}-1$ and $x_n^2-x_n-1$ have the same algebraic sign, and therefore $x_{n+2}>\varphi$ iff $x_n>\varphi$. Now $\varphi\approx 1.618$, so $x_2>\varphi$, and it follows by induction that $x_{2n}>\varphi$ for every $n\in\mathbb{Z}^+$.
Similarly, $x<\varphi$ iff $x^2-x-1<0$ if $x$ is a positive real, and $x_1=1<\varphi$, so the same induction shows that $x_{2n-1}<\varphi$ for every $n\in\mathbb{Z}^+$. Thus, $$x_1<x_3<x_5<\dots <\varphi<\dots<x_6<x_4<x_2\;.$$ In particular, the sequence of odd-numbered terms is increasing and bounded above by $\varphi$, and the sequence of even-numbered terms is decreasing and bounded below by $\varphi$, so both have limits. This doesn’t yet prove that both subsequences have the same limit, but we’re getting there. 
There are several ways to finish the job. One is to let $L$ be the limit of one of the subsequences, say the even-numbered one. Then $$L=\lim_{n\to\infty}x_{2n+2}=\lim_{n\to\infty}\frac{2x_{2n}+1}{x_{2n}+1}=\frac{2L+1}{L+1}\;,$$ so $L^2+L=2L+1$, $L^2-L-1=0$, and $L=\varphi$ (since the negative solution is plainly wrong). A similar calculation takes care of the other subsequence.
Another approach is to consider $$\left|\frac{x_{n+2}-x_{n+1}}{x_{n+1}-x_n}\right|=\left|\frac{\frac{5x_n+3}{3x_n+2}-\frac{2x_n+1}{x_n+1}}{\frac{2x_n+1}{x_n+1}-x_n}\right|=\left|\frac1{3x_n+2}\right|=\frac1{3x_n+2}<\frac12,$$ since the $x_n$ are all positive. In other words, the gap between consecutive terms shrinks at least geometrically and therefore tends to $0$, so the two subsequences must actually have the same limit, and it must satisfy $L=\frac1{L+1}$.
A: (a) Your argument shows that, if the sequence ($x_n$) converges, its limit must be $\sqrt{a}$. To show it in fact converges to $\sqrt{a}$, we note that
$$\begin{align*}x_{n+1}-\sqrt{a}
&=\frac12\left(x_n-\sqrt{a}+\frac{a}{x_n}-\sqrt{a}\right)\\
&=\frac12\left(1-\frac{\sqrt{a}}{x_n}\right)\left(x_n-\sqrt{a}\right)\\
&=\frac1{2x_n}(x_n-\sqrt{a})^2.
\end{align*}$$
Since we can show (by induction) that $x_n>0$ and $x_{n+1}\ge\sqrt{a}\ $ (for $n\ge 1$), we have
$$|x_{n+1}-\sqrt{a}|=\frac12\left|1-\frac{\sqrt{a}}{x_n}\right||x_n-\sqrt{a}|\le\frac12|x_n-\sqrt{a}|.\quad (n\ge 2)$$
Therefore $0\le |x_n-\sqrt{a}|\le \left(\frac12\right)^{n-2}|x_2-\sqrt{a}|$, and by the squeeze theorem we obtain $|x_n-\sqrt{a}|\to 0$.
(b) A similar argument can be used to show that, if the sequence ($x_n$) converges, its limit $\alpha$ must satisfy $\alpha=1+\frac1{\alpha}$. Since we can show (by induction) $x_n>0$, $\alpha=\frac{1+\sqrt5}{2}$, not $\frac{1-\sqrt5}{2}$.
To show that it in fact converges to $\alpha$, we note that
$$\begin{align*}
x_{n+1}-\alpha=\frac1{x_n}-\frac1{\alpha}=-\frac{1}{\alpha x_n}(x_n-\alpha).
\end{align*}$$
Since we can show (by induction) that $x_n\ge 1$, we have
$$|x_{n+1}-\alpha|=\left|\frac1{\alpha x_n}\right||x_n-\alpha|\le \frac1{\alpha}|x_n-\alpha|\quad \text{with}\quad 0<\frac1{\alpha}<1.$$
Therefore $0\le |x_n-\alpha|\le \left(\frac1\alpha\right)^{n-1}|x_1-\alpha|$, and by the squeeze theorem we obtain $|x_n-\alpha|\to 0$.
(P.S. It is true that "$x_{2n}$ and $x_{2n+1}$ are monotone convergent to the limit", but it is not necessary to show it here.)
A: Extended from this answer to a deleted question.
Note that all $x_n>0$ and
$$
x_{n+1}^2=\frac14\left(x_n+\frac{a}{x_n}\right)^2=\frac14\left(x_n-\frac{a}{x_n}\right)^2+a\ge a\tag{1}
$$
Thus, all $x_n$ past the first satisfy $x_n^2\ge a$. Therefore,
$$
x_{n+1}-x_n=\frac{a-x_n^2}{2x_n}\le0\tag{2}
$$
says that $x_{n+1}\le x_n$. Therefore, $\{x_n\}$ is a decreasing sequence, bounded below. Thus, the sequence converges. Furthermore, since the sequence converges,
$$
\lim_{n\to\infty}a-x_n^2=\lim_{n\to\infty}2x_n(x_{n+1}-x_n)=0\tag{3}
$$
Therefore,
$$
\lim_{n\to\infty}x_n^2=a\tag{4}
$$
A: For a):
The proof of convergence can be deduced from the question/answer LFT theory found in
Iterative Convergence Formulation for Linear Fractional Transformation with Rational Coefficients
Proof when $x_1^2 > a$
Note: If both $a$ and $x_1$ are rational numbers, then this solution is obtained  without recourse to the real number system.
Let $S$ represent $a$ and $K$ denote $x_1$.
We have our LFT theory for
$F(x) = \frac{S + Kx}{K + x}$
as espoused in the above link.
Considering Proposition 2 & 3, we have a sequence
$\{F^1, F^2, F^3, ..., F^n, ...\}$ of LFTs
with the corresponding decreasing sequence of Ks
$\{K, K_2, K_3, ..., K_n, ...\}$ and $(K_n)^2$ converges to $S$.
Might as well set $K_1$ to $K$ now.
Now with a little thought, you can see the following holds:
$K_2 = (S + K_1^2)/2K_1$
$K_4 = (S + K_2^2)/2K_2$
$K_8 = (S + K_4^2)/2K_4$
$K_{16} = (S + K_8^2)/2K_8$
etc.
But this is exactly the Babylonian Method.
So the method can  actually be described as calculating numbers that are a subsequence of our convergent sequence
$\{K_1, K_2, K_3, ..., K_n, ...\}$
So we have shown that the squares of the numbers produced by the Babylonian Method converge to $S$.
Proof when $x_1^2 < a$
Let $K$ denote $(a + x_1^2)/2x_1$. We know by the LFT theory that the square of this number is greater than $a$. So, the proof given above can now be applied, by simply 'throwing out' the first number $x_1$ of the sequence.
A: 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$.
