show that the recursive sequence converges to $\sqrt r$

Question

Let $r>0$. Show that starting with any $x_1 \neq 0 $, the sequence defined by $x_{n+1}=x_n-\frac {x^2_n-r}{2x_n}$ converges to $\sqrt r$ if $x_1 >0$ and $-\sqrt r$ if $x_1<0$.

Proof: 1. show the sequence is bounded when $x_1>0$. By induction, I can show that $x_n>0.$ 2. show that the sequence is monotone decreasing so that I can use the theorem that the monotone bounded sequence has a limit. If $x_{n+1}\le x_n$, $x^2_n-r\ge0$. But, here I cannot show that $x^2_1-r \ge 0$. How can I proceed from this step? or Is there another way to approach this question?

Thank you in advance.

Answer 1

First, let us rewrite the recursive definition by $$x_{n+1}= \frac{x_n}{2}+\frac{r}{2x_n}$$ and $$2x_{n+1} x_n = x_n^2+r.$$ If $x_1>0$, we see by induction (from the second equation) that $x_n > 0$ for all $n \in \mathbb{N}$. On the other hand, if $x_1 <0$, then $x_n <0$ for all $n \in \mathbb{N}$.

Let $x_1 >0$. If $x_1 = \sqrt{r}$, then $x_2 = \sqrt{r}$ and so on. Thus, we can assume that either $x_1 < \sqrt{r}$ or $x_1 > \sqrt{r}$. In the first case, the sequence is montone increasing and in the second case monotone decreasing.

First note that the function $f(t) = \frac{t}{2}+\frac{r}{2t}$, defined on $[0,\infty)$, is striclty monotone increasing if $t<\sqrt{r}$ and striclty decreasing if $t > \sqrt{r}$. Thus, by induction, we see that $x_n > \sqrt{r}$ if $x_1 > \sqrt{r}$ or $x_n <\sqrt{r}$ if $x_1 < \sqrt{r}$. (In the second case, we get already that the sequence is bounded!)

Now, using the same induction argument, we can prove that $x_{n+1} < x_{n}$ if $x_1 > \sqrt{r}$ or $x_{n+1} > x_n$ if $x_1 < \sqrt{r}$. (For the first case we find that the sequence is bounded.

The case $x_1 <0$ can be deduced form the previous one: Set $y_1 = -x_1$ and $y_n = - x_n$. Note that $y_{n+1} = y_n/2 + r/(2y_n)$. Thus, $y_n$ converges towards $\sqrt{r}$.

Additional Comment: This method of computing square roots is known as Babylonian method.

Answer 2

Lemma 1: For any real number $x \gt 0$, $\tag 1 x-\frac {x^2-r}{2x} \ge \sqrt r$ Proof
$x-\frac {x^2-r}{2x} \ge \sqrt r \; \text{ iff } \; 2x^2 - x^2 + r \ge 2 \sqrt r \,x \; \text{ iff } \; x^2 + r \ge 2 \sqrt r \,x \; \text{ iff } $

$\quad x^2 - 2 \sqrt r \,x + r \ge 0 \; \text{ iff }\; (x - \sqrt r)^2 \ge 0$ $\qquad \blacksquare$

We now examine the OP's question when $x_1 \gt 0$. By lemma 1, no matter what the value of $x_1$, the rest of the sequence is contained in the closed interval $[\sqrt r, +\infty)$. So without loss of generality, we can assume that $x_1 \ge \sqrt r$.

Lemma 2: For all $n \ge 1$, $\tag 2 x_{n+1} \le \sqrt r + \frac{x_{n} - \sqrt r}{2}$ Proof
Proceeding as in lemma 1, it boils down to checking an equivalent inequality,

$(x_n - \sqrt r)^2 \le x_n (x_n - \sqrt r)$

and since $x_n - \sqrt r$ is not a negative number, it is true. $\qquad \blacksquare$

Now if $x_{n}$ is at a distance to the right of $\sqrt r$ of $\kappa$, then by lemma 2, $x_{n+1}$ can be no further away from $\sqrt r$ than $\frac{\kappa}{2}$.

So the monotonic decreasing sequence must converge to $\sqrt r$.

By appealing to the symmetry, an easy argument can be made when the sequence begins at a negative number.