Using limit theorems to prove limit of recursive sequence

Question

Consider the square root approximation sequence $x_{n+1}=\frac{1}{2}(x_n+\frac{a}{x_n})$, $x_0 > a > 0$. Prove that the limit $L$ of the sequence is $\sqrt{a}$, using the limit theorems involving addition, multiplication, and division.

Answer 1

Hint

Call $\lim_{n\to \infty}x_n=L$ then apply the limit at the recurrence:

$$\lim_{n\to \infty}x_{n+1}=\frac{1}{2}\left(\lim_{n\to \infty}x_n+\frac{a}{\lim_{n\to \infty}x_n}\right)$$

Can you finish?

Answer 2

Note that

$$\frac{x_{n+1}}{\sqrt a}=\frac12\left(\frac{x_n}{\sqrt a}+\frac{\sqrt a}{x_n}\right)$$ so that it is enough to show that $$t_{n+1}=\frac12(t_n+t_n^{-1})$$ converges.

Now

$$\frac{t_{n+1}-1}{t_{n+1}+1}=\left(\frac{t_n-1}{t_n+1}\right)^2$$ so that by induction

$$\frac{t_n-1}{t_n+1}=\left(\frac{t_0-1}{t_0+1}\right)^{2^n}.$$

For positive $t_0$, the ratio on the right is smaller than $1$ (in absolute value) and the RHS converges to $0$, hence $t_n\to1$.

Answer 3

$$x_{n+1}-\sqrt{a}=\frac{(x_n-\sqrt{a})^2}{2x_n}\geq0$$ for all $n\geq0$ and $$x_{n+1}-x_n=\frac{(\sqrt{a}-x_n)(\sqrt{a}+x_n)}{2x_n}\leq0.$$

Thus, $x$ decreases for all $n\geq1$ and we got that there is a limit.

Let $x$ be the limit.

Thus, $$x=\frac{1}{2}\left(x+\frac{a}{x}\right),$$ which gives $x=\sqrt{a}$.

Done!

Answer 4

You need to show that:

$x_{n+1} = x_n \implies x_n = \sqrt a$

If the sequence converges, it must converge to $\sqrt a$

If $x_n < \sqrt a \implies x_{n+1} > \sqrt a$

$x_n > \sqrt a \implies \sqrt a < x_{n+1} < x_n$

Which sets up a sequence that is monotone and bounded, and the sequence must converge.