1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Hint: AM-GM inequality is fast. Your second approach is flawed, as the reciprocal term does not follow in the inequality * $\endgroup$ – Macavity Nov 2 '15 at 14:47
  • 1
    $\begingroup$ 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.... ) $\endgroup$ – user252450 Nov 2 '15 at 14:50
  • 2
    $\begingroup$ 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$$ $\endgroup$ – Mark Viola Nov 2 '15 at 15:00
  • $\begingroup$ @Dr.MV By far the simplest. $\endgroup$ – Did Nov 2 '15 at 15:01
  • $\begingroup$ @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. $\endgroup$ – Christian Ivicevic Nov 2 '15 at 15:08
1
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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 .

$\endgroup$
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.