real analysis - show that the recursive sequence converges to $sqrt r$

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

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.