Help with a proof that sequence of rational numbers $ a_n = \frac {a_{n-1} + \frac {2}{a_{n-1}}}{2}$ converges to an irrational, $\sqrt2$

Question

I know that there are sequences of rational numbers with irrational limits.

One in particular I've seen is $$ a_n = \frac {a_{n-1} + \frac {2}{a_{n-1}}}{2}$$ with $a_0 =1$, This is clearly rational for any $n$, but converges to $\sqrt2$ .

Can anyone provide a mathematical reasoning for this?

Answer 1

If this converges, then the limit $L$ will satisfy $L=\frac{L+2/L}{2}$. We rearrange to $2L=L+2/L$ or $L=2/L$. Cross-multiplying we get $L^2=2$ or $L=\pm \sqrt{2}$. Since every term is positive, we must have $L=\sqrt{2}$.

There are various ways to prove convergence. One powerful tool comes from dynamical systems. Consider the function $f(x)=\frac{x+2/x}{2}$. We have $f'(x)=\frac{1}{2}-\frac{1}{x^2}$. We evaluate this at $x=\sqrt{2}$, the fixed point of the iteration, to get $f'(\sqrt{2})=0$. If the result is in the interval $(-1,1)$ then iteration will converge, i.e. an attracting fixed point.

To prove convergence directly, we can prove that all terms (except $a_0$) are greater than $\sqrt{2}$, and monotonically decreasing. [Note: this method is custom-tailored to this particular sequence, and different methods will be required for other sequences.] We calculate $$\frac{a_n}{a_{n-1}}=\frac{a_{n-1}+2/a_{n-1}}{2a_{n-1}}=\frac{1}{2}+\frac{1}{a_{n-1}^2}$$ So long as $a_{n-1}>\sqrt{2}$, $\frac{1}{a_{n-1}^2}<\frac{1}{2}$ and thus the ratio $a_n/a_{n-1}<1$ so $a_n<a_{n-1}$. Since $a_1=2>\sqrt{2}$ the induction gets going properly starting with $a_1$ (not $a_0$). Now, we have a monotonically decreasing sequence of real numbers.

We need to prove this sequence is bounded below by $\sqrt{2}$. We assume $a_{n-1}>\sqrt{2}$, so $$0<(a_{n-1}-\sqrt{2})^2=a_{n-1}^2-2a_{n-1}\sqrt{2}+2$$ $$2a_{n-1}\sqrt{2}<a_{n-1}^2+2$$ $$\sqrt{2}<a_{n-1}/2+1/a_{n-1}=a_n$$

Hence $a_n>\sqrt{2}$. Now we use the completeness of the real numbers to finish the proof of convergence.

Answer 2

Stated in mathematical terms, what you have observed is that the rational numbers do not constitute a complete (metric) space. It's rather simple to construct a sequence of rational numbers converging to an irrational. One other example is the following: $$ \frac{3}{1}, \frac{31}{10}, \frac{314}{100}, \frac{3141}{1000}, \cdots $$ converging towards $\pi$.

The rationals are quite easily constructed from the integers by introducing ratios. One of the two common ways of constructing the reals from the rationals is exactly the process of adding all limmits of sequences which seem like they should converge (the technical term for such a sequence is a Cauchy-sequence, and it is the characterizing property of a complete metric space that all Cauchy sequences actually converge).

Adjoining points to a non-complete space to give all Cauchy-sequences an actual limit to converge to is called completion, and $\Bbb R$ can be (and often is) seen as nothing more than the completion of $\Bbb Q$. The other common way of constructing $\Bbb R$ is by intruducing $\sup$ to any upward bounded set by utilizing so-called Dedekind cuts. These two processes can be proven to be equivalent (and it is a common exercise in introductory analysis to do so).

Answer 3

$\pi$ is a well-known irrational number, and its decimal expansion converges to it, even though they are all numbers of the form $\mathrm{integer}/10^N$. Nothing to worry about.

Newton-Raphson's method applied to the solution of $x^2-2=0$ yields a sequence such as the one you've written, $a_{n+1}=a_n-\frac{f(a_n)}{f'(a_n)}.$

If you picture the graph of $y=f(x)=x^2-2$ and draw the tangents such as in this method, it won't surprise you that the sequence above converges (also look at conditions for the Newton method to work).

As for rational numbers converging to an irrational number, you know that the decimal system provides for finite sequences of digits converging to any real number.

Calculating decimal digits of $\pi$ is kind of a sport ($e$ was a lot easier to work out). $\pi$ is not only irrational but also (like $e$) a transcendental number (i.e., unlike $2$, there is no polynomial $f(x)=x^n+ a_1x^{n-1}+\cdots + a_0$ such that $f(\pi)=0$).

As for the speed of convergence of your sequence, $a_n\to \sqrt{2}$ but one has, in fact, that, writing $$g(x)=\frac{1}{2}\left(x+\frac{2}{x}\right),$$

that $g(\sqrt{2})=\sqrt{2}$ and that $$\lim \frac{a_{n+1}-\sqrt{2}}{a_n-\sqrt{2}}=\lim \frac{g(a_{n})-g(\sqrt{2})}{a_n-\sqrt{2}}=g'(\sqrt{2})=0.$$

One finally sees that $\frac{a_{n+1}-\sqrt{2}}{(a_n-\sqrt{2})^2}= 2 g''(\sqrt{2})=6\sqrt{2}.$

That is, if a number in the sequence approaches to, say, $n$ digits, the next one approaches to roughly $2n$ digits (the precision squares on each calculation, if sufficiently close to the limit). There are numbers such as the famous $\sum 10^{-n!}$ who are irrational (transcendental, in fact) and their decimal expansions converge extremely rapidly (this is due to Liouville).