# Approximation to $\sqrt{2}$

I'm a first year Undergraduate student from India. Our professor is going to start a Real Analysis course in September and I was preparing for the initials. I tried and solved many problems, but this one has me confused. Probably the main reason for the confusion is that my book has cited it as Hardy's problem.

If $\dfrac {m}{n}$ is a good approximation to $\sqrt{2}$, prove that $\dfrac{m+2n}{m+n}$ is a better one, and that the errors in the two cases are in opposite direction. Apply this result to show that the limit of the sequence $\dfrac{1}{1}$, $\dfrac{3}{2}$,$\dfrac{7}{5}$,$\dfrac{17}{12}$,$\dfrac{41}{29}$,.... is $\sqrt{2}$.

I need help regarding the first part of the problem, since the second part is obvious. The simpler the language, the better it is for me.

-
It seems to me as iteration method for finding fixed point for the function $f(x)=\frac{x+2}{x+1}$. (Since for $x=\frac mn$ you have $\frac{m+2n}{m+n}=\frac{x+2}{x+1}$.) – Martin Sleziak Aug 28 '11 at 14:00
I googled and found that this question is some-how connected to Continued Fraction. @Martin It Means that we're to prove $\dfrac{\sqrt{2}+2}{\sqrt{2}+1}$ is a better approximation to $\dfrac{\sqrt{2}}{1}$ than $\dfrac{m}{n}=\dfrac{\sqrt{2}}{1}$. Am I understanding wrong? – gaurav Aug 28 '11 at 14:05
@gaurav: How do you know that the sequence you obtain starting with $1/1$ converges to $\sqrt2$? A priori, the upper and lower approximations could converge to numbers strictly larger and strictly lower than $\sqrt2$, respectively. My point is, the first part of the problem should give you a "rate of convergence" that you may want to use in order to prove the second part. – Andrés E. Caicedo Aug 28 '11 at 14:20
@gaurav: $\frac{\sqrt2+2}{\sqrt2+1}=\sqrt2=\frac{\sqrt2}1$.\\ You're correct about the connection with continued fractions, but I think that you need to be familiar with theory of continuous fractions first if you want to use them for this problem. – Martin Sleziak Aug 28 '11 at 14:26
@martin Is there any better online resource than this Wikipedia article? Or I [would] have to learn it from my high school book, Higher Algebra by Hall & Knight. – gaurav Aug 28 '11 at 14:34

Suppose $\frac{m}{n}$ is slightly bigger than $\sqrt{2}$, so that we can write $\frac{m}{n}= \sqrt{2}(1+\epsilon)$ where $\epsilon >0$ is small.

Then $$\frac{m+2n}{m+n} = \frac{ \frac{m}{n} +2}{\frac{m}{n} +1} = \frac{ \sqrt{2}(1+\epsilon)+2}{\sqrt{2}(1+\epsilon) + 1} = \sqrt{2} \left(1- \left(\frac{\sqrt{2}-1}{\sqrt{2}+1+\sqrt{2}\epsilon}\right)\epsilon \right)$$

Note that $\sqrt{2}+1+\sqrt{2}\epsilon> \sqrt{2}+1$. Also, since $1<\sqrt{2}< \frac{3}{2}$, we have $\frac{\sqrt{2}-1}{\sqrt{2}+1} < \frac{1}{4}$ so ,$$\frac{\sqrt{2}-1}{\sqrt{2}+1+\sqrt{2}\epsilon}<\frac{1}{4}.$$

Thus, $\frac{m+2n}{m+n}$ is slightly smaller than $\sqrt{2}$ and it's difference from $\sqrt{2}$ is smaller in magnitude than the previous estimate, and decreases by at least a factor of $4$ with each iteration.

In a similar manner you can show the other case.

EDIT: I strengthened the estimates to address the rate of convergence issues Andres Caicedo brought up in a comment above.

-
Like a magic! Thank you! – gaurav Aug 28 '11 at 14:22
Like magic! Yes, that's why they gave you the formulas. For more advanced students, the question would be to figure this out in the first place... Perhaps do something similar for $\sqrt{3}$ or even $\sqrt[3]{2}$ – GEdgar Aug 28 '11 at 16:54
@RagibZaman What a pro... – user38268 Oct 10 '11 at 3:25

HINT $\$ Note that since $\rm\:\dfrac{m}n\:\dfrac{2\:n}m\:=\:2,\:$ one fraction is less than $\:\sqrt{2}\:$ and the other greater. Further their mediant $\rm\:\dfrac{m+2n}{n+m}\:$ is strictly between them, being the slope of the diagonal $\rm\:(n,m)+(m,2n)\:$ of the parallelogram formed by the vectors $\rm\:(n,m)\:$ and $\rm\:(m,2n)\:.\:$ To learn more search on the terms: mediant, Farey series and continued fraction.

-

We do the "opposite directions" and "better approximation" parts, including an estimate of how much better.

We are intended to assume that $m$ and $n$ are positive, and indeed that they are positive integers. In the argument below, we do not need $m$ and $n$ to be integers, but we do assume they are positive. Some assumption needs to be made, since $m=-1$, $n=1$ quickly leads to disaster!

Look at $$\frac{m+2n}{m+n}-\sqrt{2}.$$ This is equal to $$\frac{m+2n-m\sqrt{2}-n\sqrt{2}}{m+n},$$ which in turn is equal to $$-\frac{(\sqrt{2}-1)(m-n\sqrt{2})}{m+n}.$$ Divide top and bottom by $n$. We get that the above expression is equal to $$-\frac{(\sqrt{2}-1)(\frac{m}{n}-\sqrt{2})}{1+\frac{m}{n}}.$$ So we conclude that $$\frac{m+2n}{m+n}-\sqrt{2}=\left(-\frac{\sqrt{2}-1}{1+\frac{m}{n}}\right)\left(\frac{m}{n}-\sqrt{2}\right).$$

Note that the "multiplication factor" $-\frac{\sqrt{2}-1}{1+\frac{m}{n}}$ is negative. That means that if $\frac{m}{n}-\sqrt{2}$ is negative, then $\frac{m+2n}{m+n}-\sqrt{2}$ is positive, and if $\frac{m}{n}-\sqrt{2}$ is positive, then $\frac{m+2n}{m+n}-\sqrt{2}$ is negative. Thus the approximations alternate between too big and too small.

Note also that the multiplication factor $-\frac{\sqrt{2}-1}{1+\frac{m}{n}}$ has absolute value less than $\sqrt{2}-1$, which is less than $0.5$. So the absolute value of the error when we approximate $\sqrt{2}$ by $\frac{m+2n}{m+n}$ is less than half the absolute value of the error when we approximate $\sqrt{2}$ by $\frac{m}{n}$.

Note that we can make a better estimate of the rate of approach to $\sqrt{2}$, if we assume that we start with $m=n=1$. For then, forever, our approximation will be bigger than $1$, so the multiplication factor has absolute value $(\sqrt{2}-1)/(1+m/n)$, which is less than $(\sqrt{2}-1)/2$.

-
You can do the same with simpler formulas, by squaring and subtracting 2: if the error of the $k$-th element of the sequence is $e_k = \left(\dfrac{m}{n}\right)^2 - 2 = \dfrac{m^2-2n^2}{n^2}$, the error for the next element is $e_{k+1} = \left(\dfrac{m+2n}{m+n}\right)^2 - 2 = \dfrac{2n^2-m^2}{(m+n)^2} = -e_k \left(\dfrac{n}{m+n}\right)^2$. Assuming $m+n > 0$ the sequence $|e_k|$ is monotonic decreasing and converging to zero, so $e_k$ is also converging to zero. For the particular sequence starting at $1/1$, the numerators of $e_k$ alternate between 1 and -1. – Paolo Bonzini Aug 30 '11 at 7:11
@Paolo Bonzini: That is a nice way to look at it. It could serve as a start to showing the connections between solutions of the Pell Equations $x^2-2y^2=\pm 1$ and certain "good" approximations of $\sqrt{2}$. – André Nicolas Aug 30 '11 at 9:13

First, let $x_k = \frac{m}{n}$, then $x_{k+1} = \frac{x_k +2}{x_k+1}$.

Notice that $x_{k+1} - x_k = \frac{2-x_k^2}{1+x_k}$ and that $x_{k+1}^2 - 2 = \frac{2-x_k^2}{(1+x_k)^2}$.

Thus if $0< x_k <\sqrt{2}$, then $x_{k+1} > \sqrt{2}$. Also from here

$$\vert x_{k+1}^2 - 2 \vert < \vert x_k^2 - 2 \vert$$ for $x_k > 0$. Thus $x_k$ converges to $\sqrt{2}$ and $x_k - \sqrt{2}$ is an alternating sequence.

-

A somewhat surreal and lazy solution using Mathematica to make things easier:

(* your two guesses *)
guess1 = m/n
guess2 = (m+2*n)/(m+n)

(* if you square your guesses and subtract from 2, you get signed
closeness to 2; squaring again eliminates the sign *)

dist1 = (guess1^2-2)^2
(-2 + m^2/n^2)^2

dist2 = (guess2^2-2)^2
(m^2 - 2*n^2)^2/(m + n)^4

(* We want dist2 < dist1; under what cases can that fail? *)
Reduce[{dist1 <= dist2, m>0, n>0}, Reals]
n > 0 && m == Sqrt[2]*Sqrt[n^2]


So, the only case where dist1 is even EQUAL to dist2 is when m/n is Sqrt[2], which is, of course, impossible.

-