4
$\begingroup$

$x_n= \dfrac{x_{n-1}}{2} + \dfrac{1}{x_{n-1}}$

I know it converges to $\sqrt2$ and I do not want the answer. I just want a prod in the right direction.

I have tried the following and none have worked: $x_n-x_{n-1}$ and this got me nowhere.

I have tried $\dfrac{x_{n+1}}{x_{n}}$ with no luck, and I was expecting this to help,

enter image description here

$\endgroup$
  • 2
    $\begingroup$ Prod: Plot the graphs of the function $x\mapsto\frac{x}2+\frac1{x}$ and $x\mapsto x$ on the same diagram. $\endgroup$ – Did May 7 '16 at 5:37
  • $\begingroup$ So I have done this and found they intersect at $\sqrt2$ in the 1st quadrant. $\endgroup$ – stackdsewew May 7 '16 at 5:44
  • 1
    $\begingroup$ Right, and now did you visualize a sequence $(x_n)$ on the graph thanks to the usual ladder-like construction? What does this suggest? $\endgroup$ – Did May 7 '16 at 5:46
  • 2
    $\begingroup$ I fail to see any ladder-like construction... Anyway, it should be clear that after at most one iteration, $x_n\geqslant\sqrt2$ and that, after that, $(x_n)$ is nonincreasing. Can you show these? Once this is done, a natural idea is to compute $x_{n+1}-\sqrt2$ in terms of $x_n-\sqrt2$ and possibly of other quantities and to see what happens. Did you do that? Another natural idea is to check that $(x_n)$ is decreasing and to conclude directly from this as the answerer below did. Actually, the whole point of the graph is to suggest tons of properties of $(x_n)$ to prove to get the conclusion. $\endgroup$ – Did May 7 '16 at 5:53
  • 1
    $\begingroup$ Note that this is the Newton iteration for the square root $x_n=\frac12(x_{n-1}+a/x_{n-1})$, with $a=2$. $\endgroup$ – Yves Daoust May 7 '16 at 13:21
5
$\begingroup$

We have: By AM-GM inequality: $x_n > 2\sqrt{\dfrac{x_{n-1}}{2}\cdot \dfrac{1}{x_{n-1}}}=\sqrt{2}, \forall n \geq 1$. Thus: $x_n-x_{n-1} = \dfrac{1}{x_{n-1}} - \dfrac{x_{n-1}}{2}= \dfrac{2-x_{n-1}^2}{2x_{n-1}} < 0$. Hence $x_n$ is a decreasing sequence,and is bounded below by $\sqrt{2}$. So it converges, and you showed the limit is $\sqrt{2}$.

$\endgroup$
2
$\begingroup$

Observe that

$$\frac{x_n-\sqrt2}{x_n+\sqrt2}=\frac{\dfrac{x_{n-1}}{2} + \dfrac{1}{x_{n-1}}-\sqrt2}{\dfrac{x_{n-1}}{2} + \dfrac{1}{x_{n-1}}+\sqrt2}=\frac{x_{n-1}^2-2\sqrt2x_{n-1}+2}{x_{n-1}^2+2\sqrt2x_{n-1}+2}=\left(\frac{x_{n-1}-\sqrt2}{x_{n-1}+\sqrt2}\right)^2.$$

Then by induction,

$$\frac{x_n-\sqrt2}{x_n+\sqrt2}=\left(\frac{x_0-\sqrt2}{x_0+\sqrt2}\right)^{2^n}.$$

Then whenever

$$\left|\frac{x_0-\sqrt2}{x_0+\sqrt2}\right|<1$$ (in particular $x_0>0$) the series converges to $\sqrt2$.

$\endgroup$
1
$\begingroup$

Let $f(x)=x^2-2$, note that $f$ is convex and hence it is straightforward to show that if $x_n$ is the Newton iteration for the equation $f(x) = 0$, and $x_0>0$, then $x_n \ge \sqrt{2}$ (equivalently, $f(x_n) \ge 0$) if $n \ge 1$, and $\sqrt{2} \le x_{n+1} \le x_n$ for $n \ge 1$.

$\endgroup$
  • $\begingroup$ Sorry if it is a silly question but how does your last inequality prove convergence Is it similar to a squeeze theorem like principle? $\endgroup$ – stackdsewew May 7 '16 at 13:36
  • $\begingroup$ @anna_xox: The same was as in the accepted answer, for $n \ge 1$, the sequence $x_n$ is non increasing and bounded below by $\sqrt{2}$, hence it converges to some $x$. Since $f(x) = 0$, we see that $x= \sqrt{2}$. $\endgroup$ – copper.hat May 7 '16 at 22:27

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.