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. 
 A: 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.
A: 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.
