For $a>0$ and $x_0\ge a$ prove that the sequence defined as $x_{n+1}=(x_n+a/x_n)/2$ decreases and converges to $\sqrt a$

Solution 1:

The sequence being decreasing means $x_{n+1}<x_n$, for all $n$. This becomes $$ x_n+\frac{a}{x_n}<2x_n $$ that is, $x_n^2>a$, because it is obvious that $x_n>0$ for all $n$. I believe that the statement should have $x_0^2>a$. For instance, if $a=1/4$ and $x_0=1/3$, we have $x_0^2<a$, which implies $x_1>x_0$.

So, I'll go with $x_0^2>a$ as the hypothesis, which is the base step in the induction proof.

Suppose $x_n^2>a$. Then $x_{n+1}^2-a$ becomes $$ x_{n+1}^2-a=\frac{1}{4}\left(x_n+\frac{a}{x_n}\right)^{\!2}-a= \frac{1}{4}\left(x_n^2+2a+\frac{a^2}{x_n^2}-4a\right)= \frac{1}{4}\left(x_n-\frac{a}{x_n}\right)^{\!2}>0 $$

If the hypothesis is $x_0>a$, then the sequence need not be decreasing, as shown before. Of course, if we assume $a>1$, then $x_0>a$ implies $x_0^2>a$, because from $x_0>a>1$ we get $$ x_0^2>ax_0>x_0>a $$

So the statement should have either $x_0^2>a$ or $a>1$. In the case $x_0>a$ and $0<a\le1$ we may indeed obtain an oscillating sequence.

Solution 2:

Let $f(x)=\frac{1}{2}(x+\frac{a}{x})$

$f$ has two fixed points

$x=\sqrt{a}$ and $x=-\sqrt{a}$

those are possible limits of the sequence $(x_n)$ such that

$x_0\geq a>0$ and

$x_{n+1}=f(x_n)$.

by induction we can easily prove that

$\forall n\in \mathbb N \; x_n>0$

thus if $(x_n)$ converges, the limit will be $\sqrt{a}$ as $f$ is continuous at $(0,+\infty)$.

on the other hand,

$f'(x)=\frac{1}{2}\frac{x^2-a}{x^2}$.

$f(x)-x=\frac{1}{2}\frac{a-x^2}{x}$.

now let us discuss three cases.

FIRST

$x_0=\sqrt{a}$. in this case, the sequence is constant and convergent.

SECOND

$x_0>\sqrt{a}$ by induction we prove that in this case $\forall n \; x_n \in (\sqrt{a},+\infty)$ as $f$ is increasing.

thus

$f(x_0)-x_0<0 \implies x_1<x_0$

and also by induction we get $x_{n+1}<x_n$

finally $(x_n)$ decreases and $\sqrt{a}<x_n \implies $(x_n)$ converges to $\sqrt{a}$.

THIRD CASE

$x_0<\sqrt{a}$ this case is little more difficult since $f$ is decreasing and i think that your hypothesis should be $x_0\geq\sqrt{a}$.