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.

  • $\begingroup$ I do not have the capacity of solving this problem, but I just want to say that it has been at least $2$ hours and no other users have replied to this question. I suggest placing a bounty on it (which I believe can only be done three days after the question has been posted, but correct me if I am wrong). $\endgroup$ – Mr Pie Mar 21 '18 at 8:26

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.

  • 1
    $\begingroup$ A nice solution, but its third paragraph can be slightly simplified. If $0 < x_n < \sqrt{r}$ then $x_n^2 < r$; so, from the second equation we get $2 x_{n+1} x_n > 2 x_n^2$, hence $x_{n + 1} > x_n$ (and analogously for $x_n > \sqrt{r}$). And it doesn't use monotonicity of a function. $\endgroup$ – user539887 Mar 21 '18 at 10:09
  • $\begingroup$ It is a nice proof. Thanks. $\endgroup$ – DEJABLUE Mar 22 '18 at 6:20

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.


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.