Why does $ a_n = \frac {a_{n-1} + \frac {2}{a_{n-1}}}{2}$ converge to an irrational number?

Question

There is a problem in my textbook that goes like this

$$ a_n = \frac {a_{n-1} + \frac {2}{a_{n-1}}}{2}$$

and

$$a_0 =1$$

for all $n\ge1$.

It is monotonically decreasing sequence of rational numbers and bounded below. However, it cannot converge to a rational number.

Then the task is to find the limit. The problem itself is easy but I don't understand how the author judged the limit to be irrational even before solving the question? Is there any property or did they just know the answer beforehand?

Answer 1

Yep, the author knew the answer beforehand, I would say much longer before.

Because this is just an instance of the Babylonian method of computing square roots, later discovered to be a particular case of Newton's iterative method for the resolution of nonlinear equations.

So with closed eyes, this sequence converges to $\sqrt2$. You can easily verify it be assuming convergence, so that $a_{n-1}$ and $a_n$ become indiscernible, and

$$a=\frac{a+\dfrac2a}{2}$$ or $$a^2=2.$$ As the initial value is $1$, all terms are positive and convergence is to the positive root (if there is convergence, though).

---

There is a simple way to explain that method, also known as Heron's formula.

Let $s$ be the number of which you want to extract the root, and let $a$ be an approximation by default. Then $$a<\sqrt s\implies a':=\frac sa>\sqrt s$$ so that $\dfrac sa$ is another approximation, by excess. Now if we take the arithmetic mean, we get a new approximation which is closer than the worse of the two,

$$a''=\frac{a+a'}2=\frac{a+\dfrac sa}{2}.$$

As can be shown, when you are close to the root, the sequence converges extremely rapidly.

For example,

$$a=\color{green}{1.41}\implies a'=\color{green}{1.41}84397163121\cdots\implies a''=\color{green}{1.41421}9858156\cdots$$ while the true value is $$\sqrt2=1.4142135623731\cdots$$

The next iteration gives $11$ exact digits.

---

A note on convergence, for the skepticals (the method has been in use for at least two millenia).

Let $$x_n:=\frac{a_n}{\sqrt s}.$$

We have

$$\frac{x_{n+1}-1}{x_{n+1}+1}=\frac{x_n+\dfrac1{x_n}-2}{x_n+\dfrac1{x_n}+2}=\frac{(x_n-1)^2}{(x_n+1)^2}$$ and by induction

$$\frac{x_n-1}{x_n+1}=\left(\frac{x_0-1}{x_0+1}\right)^{2^n}.$$

This is an exact formula for the $n^{th}$ iterate, which proves convergence from any $x_0$ such that

$$\left|\frac{x_0-1}{x_0+1}\right|<1.$$

This holds for all positive $x_0$.

In passing, this also proves quadratic convergence, i.e. the relative error is squared on every iteration.

Answer 2

Suppose $f(x)=x^2-2$ so roots are $\pm \sqrt2$ now use Newton method $$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}$$ so you will have $$x_{n+1}=x_n-\frac{x_n^2-2}{2x_n}\\=\frac{\frac{2x_n^2-x_n^2+2}{x_n}}{2}\\=\frac{x_n+\frac{2}{x_n}}{2}$$ now take $x_n \to a_n$ so $$a_n = \frac {a_{n-1} + \frac {2}{a_{n-1}}}{2}$$ and note $a_n $ tends to $\sqrt 2 ,if \space a_1>0$ , tends to $-\sqrt 2 ,if \space a_1<0 $ by iteration.
$\bf remark:$ there are some equation like this which work with rational numbers and finally get irrational ... for example :$\sum _{n=1}^{\infty}\frac{1}{n^2}=\frac{\pi^2}{6}\\\text{sum of rationals = irrational}$

Answer 3

Rewrite $$a_n = \frac {a_{n-1} + \frac {2}{a_{n-1}}}{2}$$ as $$a_n=a_{n-1}-\frac 12a_{n-1}+\frac 1{a_{n-1}}=a_{n-1}-\frac{a^2_{n-1}-2 }{2a_{n-1}}$$ and recognize the Newton formula for the solution of $x^2-2=0$.

Answer 4

Because if $a$ is the limit then $a^2=2$, which gives $a=\sqrt2$, which is an irrational number.

$$a_{n}-\sqrt2=\frac{(a_{n-1}-\sqrt2)^2}{2a_{n-1}}>0$$ and $$a_n-a_{n-1}=\frac{1}{a_{n-1}}-\frac{a_{n-1}}{2}=\frac{2-a_{n-1}^2}{2a_{n-1}}<0,$$ which gives that our sequence converges.