How to prove the sequence $x_{n+1} = \frac{x_n}2 + \frac 1{x_n}$ is a Cauchy sequence

Question

Here is a question I do not know how to prove. Thanks for your helping！

Prove that the sequence $$x_{n+1} = \dfrac{x_n}2 + \dfrac 1{x_n}, x_0 = 1$$is a Cauchy sequence.

Answer 1

First, notice that $$\frac{x_{n+1}}{x_n} = \frac{1}{2} + \frac{1}{x_{n}^2}$$ which is $\leq 1$ if and only if $x_n^2 \geq 2$.

We can rearrange the recurrence to get $$2x_{n+1}x_n = x_n^2 + 2$$ Then note that $$\begin{align} (x_{n+1} - x_n)^2 &= x_{n+1}^2 - 2x_{n+1}x_n + x_n^2 \\ &= x_{n+1}^2 -x_n^2 - 2 + x_n^2 \\ &= x_{n+1}^2 - 2\\ \end{align}$$ Since the left hand side is nonnegative, so is the right hand side, so this shows that $x_{n+1}^2 \geq 2$ for all $n$, i.e. $x_n^2 \geq 2$ for all $n \geq 1$.

Additionally, the original recurrence shows that $x_{n+1} > 0$ if $x_n > 0$, and since $x_0 = 1 > 0$, it follows that $x_n > 0$ for all $n$. Therefore $x_n^2 \geq 2$ implies $x_n \geq \sqrt{2}$.

Combining this with the observation in the first paragraph, we see that $x_{n+1} \leq x_n$ for all $n \geq 1$. Therefore for $n \geq 1$, $(x_n)$ is a decreasing sequence which is bounded below (by $\sqrt{2}$), hence it is a convergent sequence, hence it is a Cauchy sequence.

Incidentally, the limit $L$ must satisfy $$L = \frac{L}{2} + \frac{1}{L}$$ which shows that the limit is in fact equal to $\sqrt{2}$.

Answer 2

This is an example of the Newton method. But to give a proof we show that the series is decreasing and bounded below, it therefore converges and so is Cauchy.

The inequality

$$\sqrt{2}\leq \frac{x_n^2+2}{2x_n}$$ is equivalent with

$$0\leq (x_n-\sqrt{2})^2$$

and $x_{n+1} \leq x_n$ now follows immediately using the recursion formula.

Answer 3

Another method:

Firstly a bit of pedantry. The sequence is decreasing only after the second element. The first three elements of the sequence are $ 1, \frac{3}{2}, \frac{17}{12} $.

Now consider the function $f$ which takes $ x_n \to x_{n + 1} $.

$$ f(x) = \frac x 2 + \frac 1 x \implies f'(x) = \frac{x^2 - 2}{ 2x^2 }$$

$ f' \gt 0 $ if $ x \gt \sqrt 2 $ and $ f' \lt 0 $ if $ x \lt \sqrt 2 $. So for $ x \gt \sqrt 2 $ the function $f$ is increasing.

We will prove by induction the statement:

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; P(n)$: $\;\; \sqrt 2 \lt x_{n + 1} \lt x_n \;\;$ for $ n \ge 1 $.

It must first be verified that $ x _1 = \frac 3 2 $ and $ x_2 = \frac{17}{12} $ are both numbers greater than $\sqrt 2$ which can be done by squaring both sides. Then the statement is true for $n = 1$. Suppose $P(n)$ is true for arbitrary $n \in \Bbb N$. Then,

$$ \sqrt 2 \lt x_{n + 1} \lt x_{n} \implies f(x_{n + 1}) \lt f(x_{n }) \implies \sqrt 2 \lt x_{n + 2} \lt x_{n + 1} $$

which requires another small observation (to claim $ f(x_{n + 1}) \gt \sqrt 2 $) $$f(x) = \dfrac{x^2 + 2}{2x} = \dfrac{(x - \sqrt 2)^2 + 2 \sqrt 2 x}{2x} = \dfrac{(x - \sqrt 2)^2}{2x} + \sqrt 2 \gt \sqrt 2 \; \text {if} \; x \gt \sqrt 2$$

Hence $P(n)$ is true for all $n \in \Bbb N$. Hence $(x_n)$ is decreasing and is bounded below by $\sqrt 2$. Hence

$$ (x_n) \; \text{converges} \iff (x_n) \; \text{is a Cauchy sequence} $$