Does this recurrence relation converge?

Question

I did an exam last week and was asked whether $$x_1 = 2,\quad x_{n+1} = x_n - \frac{ x_{n}^2 - 2}{2x_n};$$ converges or not. I wrote that it did and converged to $\sqrt{2}$. I was not able to prove that this converges but by substituting $x_n$ for $L$, I got this answer. Am I correct?

Answer 1

First rewrite $x_{n+1} = \frac{x_n}{2} + \frac{1}{x_n}$, this makes it a bit simpler. Next, try to prove that for all positive integers $n$:

1. $x_n > 0$
2. $x_n > \sqrt{2}$
3. $x_{n+1} < x_{n}$

(In that order.)

Then we know $(x_n)_n$ is a bounded, descending sequence. Therefore it must converge!

Then we can take limits in the equation (so replace $x_n$ and $x_{n+1}$ by the limit L, like you did) and find that this limit is indeed $\sqrt{2}$. (The equation will have another solution, namely $-\sqrt{2}$, but this one cant be the limit since all $x_n > 0$.)

The key in this exercise is to first prove that the sequence converges. Only then we are allowed to take limits, and find the limit as you described. (Although you might want to calculate the limit first, since it could be helpful in proving that the sequence converges, like in step 2.)

Answer 2

The answer is correct but a proof or even a slightest justification is required.

$x_n$ converges to $\sqrt 2$ because it is Newton’s method for finding roots applied to $f(x)=x^2-2$ with an appropiate initial guess.