# 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?

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

2. 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 it's 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?

-
This link might be useful for a: proofwiki.org/wiki/… – Martin Sleziak Nov 17 '11 at 20:26
oops martin, sorry, you're right! – Clash Nov 17 '11 at 20:33
When you (or someone) cleverly noticed that $x_n=\frac{F_{n+1}}{F_n}$, where $F_n$ is the $n$-th term of Fibonacci sequence, you could use show this by induction. Then you can find $x_{n+1}-x_n=\frac{F_{n+2}}{F_{n+1}}-\frac{F_{n+1}}{F_n}=\frac{F_nF_{n+2}-F_{n+1‌​}}{F_nF_{n+1}}=(-1)^{n+1}\frac1{F_nF_{n+1}}$, using Cassini's identity. This means that the sequence is alternating and that $\frac1{|x_n-x_{n+1}|}\to0$. \\ This is basically the suggestions from Aryabhata's answer. – Martin Sleziak Nov 17 '11 at 21:01

(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}$.

-
hi brian, thanks for the reply. I think I have to prove this with induction, but I'm lost as to which step to do or what the beginning of the induction is. any tips? – Clash Nov 16 '11 at 15:05
@Clash: Induction looks good. Note that $x_{n+2}=1+\frac1{x_{n+1}}=1+\left(1+\frac1{x_n}\right)^{-1}=$ $1+\frac{x_n}{x_n+1}=\frac{2x_n+1}{x_n+1}$. When is $\frac{2x_n+1}{x_n+1}<x_n$, and when is $\frac{2x_n+1}{x_n+1}>x_n$? What is $x_{n+4}$ in terms of $x_n$? Try using this to show that if $x_{n+2}<x_n$, then $x_{n+4}<x_{n+2}$, and similarly for $>$. – Brian M. Scott Nov 16 '11 at 15:23
Brian, I swear I'm trying to solve it since I posted. I just can't move forward. All I got was $x_{n+2} > x_n$, when $x_n^2 < x_n + 1$. As all the values are contained in [1, 2], I guess this does make some sense. I then reached your answer at $\varphi$. I suppose I'm trying to solve it with the wrong tools. – Clash Nov 16 '11 at 15:52
So, $x_{n+2} > x_n$ until $x_n < \varphi = \frac12(1+\sqrt 5)$? – Clash Nov 16 '11 at 15:54
@Clash: With a bit of algebra you get $x_{n+4}=\frac{5x_n+3}{3x_n+2}$, which is $>\frac{2x_n+1}{x_n+1}$ iff $x_n^2-x_n-1<0$, which is exactly the condition that you found was equivalent to $x_{n+2}>x_n$. Thus, $x_{n+4}>x_{n+2}$ iff $x_{n+2}>x_n$; since $x_1<x_3$, the fact that the odd-numbered terms are increasing follows by induction. Now do the same thing with $<$ and the even-numbered terms. – Brian M. Scott Nov 16 '11 at 16:09

(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.)

-

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}$).

-
what's AM and GM? – Clash Nov 17 '11 at 18:36
@Clash en.wikipedia.org/wiki/… – pharmine Nov 18 '11 at 3:16

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}$$

-

Following robjohn note that $$x_{n+1} \le x_n$$ and by AM-GM inequality, $$|x_{n+1}|=\frac{1}{2}|x_n+\dfrac{a}{x_n}| \ge \sqrt{x_n.\frac{a}{x_n}}=\sqrt{a}$$ By monotone convergent theorem $\lim_{n \to \infty}x_n=x$ is exist as a real number.
Note that $x^2=a.$

-