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

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?


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.


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


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


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.