Approximation of $\sqrt{2}$.

Question

Let $(x_n)$ be the sequence define by \begin{cases} x_1 = 1 \\ x_{n+1} = \frac{1}{2}\left( x_n + \frac{2}{x_n} \right) \end{cases}. Show that $1\leqslant x_n \leqslant\frac{3}{2}\ \forall n\in\mathbb{N}$.

I've tried by induction. My induction hypothesis was the vadility of $1\leqslant x_k \leqslant\frac{3}{2}$ for some $k\in\mathbb{N}$. From that it is easy to show that $x_{k+1}\geqslant 1$. In fact, $1\leqslant x_k$ implies $3\leqslant x_k^2+2$ and $x_k\leqslant\frac{3}{2}$ implies $1\leqslant\frac{3}{2x_k}$. Then, \begin{align} x_{k+1} &= \frac{x_k^2+2}{2x_k}\\ &\geqslant \frac{3}{2x_k}\\ &\geqslant 1. \end{align} But I'm stuck with $x_{k+1}\leqslant\frac{3}{2}$. I only get $x_{k+1}\leqslant\frac{17}{8}$, way over $\frac{3}{2}$. I think there must be some preliminay result that makes this last part easier, but I do not know. Any hint would be enough. Thanks in advance.

Answer 1

I've discussed this question with a friend and he gave me a excellent idea as I insisted in proving it by induction. Follow the last part for $x_{k+1}\leqslant\frac{3}{2}$:

First notice that

\begin{align} x_{k+1} - \frac{3}{2} &= \frac{x_k}{2} + \frac{1}{x_k} - \frac{3}{2} \\ &= \frac{ x_k^2 - 3x_k + 2 }{ 2x_k } \\ &= \frac{(x_k-1)(x_k-2)}{ 2x_k } \end{align}

Now, looking at that last quotient, with the inductive hypothesis in mind, we have $x_k-1\geqslant 0$ and $x_k\leqslant\frac{3}{2}<2\ \therefore\ x_k-2 < 0$. Which let us conclude \begin{equation} x_{k+1} - \frac{3}{2} = \frac{ (x_k-1)(x_k-2) }{ 2x_k } \leqslant 0 \quad \implies \quad x_{k+1}\leqslant\frac{3}{2}. \end{equation}

I appreciated all solutions in here.

Answer 2

The sequence $x_n$ is decreasing after the second term, which is $3/2$.

Proof:

First,

$$x_{n+1}-\sqrt2=\frac{1}{2x_n}(x_n-\sqrt2)^2\ge0$$

Therefore $x_n\ge\sqrt{2}$ for all $n>1$.

And

$$x_{n+1}-x_n=\frac{1}{2}(\frac{2}{x_n}-x_n)$$

But for $n>1$, $x_n\ge\sqrt2$ hence $\dfrac{2}{x_n}\le\sqrt2$ and $x_{n+1}-x_n\le0$.

Therefore, $\sqrt2\le x_n\le\frac32$ for all $n>1$, and $1\le x_n\le\frac32$ for all $n\ge1$.

Answer 3

This is just Newton's method. However, since the $x_n$ values are rational, we have an alternative for discussing the accuracy..

We begin with $x = \frac{3}{2},$ that is rational $x = \frac{p}{q}$ with $p^2 - 2 q^2 = 1.$ The next step turns out the same: if $x_n = \frac{p}{q}$ with $p^2 - 2 q^2 = 1,$ then calculation gives $$x_{n+1} = \frac{p^2 + 2 q^2}{2pq}$$ Then we ask about $$ (p^2 + 2 q^2)^2 - 2 (2pq)^2 = p^4 + 4 p^2 q^2 + 4 q^4 - 8p^2 q^2 = (p^2 - 2 q^2)^2 = 1 $$

Next, how good is the approximation to $\sqrt 2?$ When $p^2 - 2 q^2 = 1,$ we have $ \left( \frac{p}{q} \right)^2 - 2 = \frac{1}{q^2} ,$ so a quick outcome is $\frac{p}{q} > \sqrt 2 $ and $\frac{p}{q} + \sqrt 2 > \sqrt 8,$ after which $\frac{1}{\frac{p}{q} + \sqrt 2} < \frac{1}{\sqrt 8}.$ But $$(\frac{p}{q} + \sqrt 2) (\frac{p}{q} - \sqrt 2) = \frac{1}{q^2}, $$ $$\frac{1}{\frac{p}{q} + \sqrt 2} < \frac{1}{\sqrt 8},$$ $$ (\frac{p}{q} - \sqrt 2) < \frac{1}{q^2 \, \sqrt 8 \;} \; . $$