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

Question

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?

Answer 1

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}$$

Answer 2

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

Answer 3

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 .

Answer 4

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}$.