# Prove that $x_{n+1}=\frac{x_n}{2}+\frac{1}{x_n}\geq\sqrt{2}$

Let $(x_n)_{n\in\mathbb N}$ be a recursively defined sequence with $x_1=9$ and $$x_{n+1}=\frac{x_n}{2}+\frac{1}{x_n}\text{ for }n\geq 1.$$ Show that $x_n\geq\sqrt{2}$ for all $n$.

Because $x_n\geq 0$ one can easily prove inductively that $$x_n^2\geq 2\Leftrightarrow x_n^2-2\geq 0\Leftrightarrow\left(\frac{x_{n-1}}{2}-\frac{1}{x_{n-1}}\right)^2\geq 0,$$ hence $x_n\geq\sqrt{2}$. However I have seen another approch which I was very curious about because I don't have the feeling that this can be done without proper justification other than the induction hypothesis:

$$x_{n+1}=\frac{x_n}{2}+\frac{1}{x_n}\overset{(*)}{\geq}\frac{\sqrt{2}}{2}+\frac{1}{\sqrt{2}}=\sqrt{2}$$

For $(*)$ it is assumed that $x_n\geq\sqrt{2}$ holds for an $n\in\mathbb N$. Are there any objections about this consideration?

• Hint: AM-GM inequality is fast. Your second approach is flawed, as the reciprocal term does not follow in the inequality * – Macavity Nov 2 '15 at 14:47
• The inequality $\frac{1}{x_n} \geq \frac{1}{\sqrt{2}}$ is false because it would imply that $x_n \leq \sqrt{2}$ (this is true only if $x_n=\sqrt{2}$ but else.... ) – user252450 Nov 2 '15 at 14:50
• A straightforward approach to showing that $x_n\ge \sqrt{2}$ is to write $$x_{n}-\sqrt{2}=\left(\frac{x_{n-1}}{2}+\frac1{x_{n-1}}\right)-\sqrt{2}=\frac{(x_{n-1}-\sqrt{2})^2}{2x_{n-1}}\ge0$$ – Mark Viola Nov 2 '15 at 15:00
• @Dr.MV By far the simplest. – Did Nov 2 '15 at 15:01
• @Dr.MV Yeah pretty similiar to my explained approach in the first part of my post. I was just wondering about the other approach and its correctness there. – Christian Ivicevic Nov 2 '15 at 15:08

Yes, you can make the assumption $x_n\ge \sqrt{2}$ to prove $x_{n+1}\ge \sqrt{2}$ as per strong form of mathematical induction.

But your reasoning is wrong as $x_n\ge \sqrt{2} \Rightarrow \frac{1}{x_n} \le \frac{1}{\sqrt{2}}$.

Better is to use AM-GM inequality as Macavity has mentioned since the quantities are all positive.

$$\frac{\frac{x_n}{2}+\frac{1}{x_n}}{2}\ge \sqrt{\frac{x_n}{2}\cdot\frac{1}{x_n}}$$ $$x_{n+1}\ge \sqrt{2}$$

If you know derivatives you can make it work as follows. Consider the function : $$f(x)=\frac{x^2+2}{2x}$$ Now calculate the derivative : $$f'(x)=\frac{2x^2-4}{4x^2}\geq 0$$ if $x\geq \sqrt{2}$ so the function is increasing for $x\geq \sqrt{2}$

Now from the induction hypothesis $x_n\geq \sqrt{2}$ so from the monotony : $$x_{n+1}=f(x_n)\geq(\sqrt{2})=\frac{4}{2\sqrt{2}}=\sqrt{2}$$ as wanted .

Although the following goes a bit beyond addressing the OP's question, I thought that it would be instructive. So, let's have a look at the sequence generated by the recurrence relationship $x_n=\frac12 x_{n-1}+\frac{1}{x_{n-1}}$.

This is actually an interesting recursively generated sequence. If we examine the first difference $x_{n}-x_{n-1}$ we find that

$$x_{n}-x_{n-1}=\frac{2-x_{n-1}^2}{2x_{n-1}} \tag 1$$

We deduce immediately from $(1)$ that if $x_n > \sqrt{2}$, then $x_n$ is decreasing while if $x_n<\sqrt{2}$, then $x_n$ is increasing.

Now, a straightforward approach to showing that $x_n\ge \sqrt{2}$ is to write

$$x_{n}-\sqrt{2}=\left(\frac{x_{n-1}}{2}+\frac1{x_{n-1}}\right)-\sqrt{2}=\frac{(x_{n-1}-\sqrt{2})^2}{2x_{n-1}}\ge0 \tag 2$$

regardless of the value of $x_{n-1}$.

Therefore, the only value of the sequence that can ever be less than $\sqrt{2}$ is its initial "seed" value. From $(1)$, we see that if the seed value is less than $\sqrt{2}$, the subsequent value increases. And $(2)$ shows that it increases above $\sqrt{2}$. Then, the remaining sequence decreases monotonically to the limit value of $\sqrt{2}$.

Hint: study the function $f(x)=x/2 +1/x$ it increases if $x>\sqrt2$