# How prove $\lim x_n = \sqrt{\frac{a}{b}}$ if $b \neq 0$ for $x_1=c$ and $x_{n+1}=\frac{x_n^2 + \frac{a}{b}}{2x_n}$?

Let $x_1=c$ and $x_{n+1}=\frac{x_n^2 + \frac{a}{b}}{2x_n}$. How prove $\lim x_n = \sqrt{\frac{a}{b}}$ if $b \neq 0$ ?

• If it exists, it will satisfy $L=\frac{L^2+\frac{a}{b}}{2L}$. (Take the limit of both sides of the recurrence relation). – Michael Burr Jul 13 '15 at 5:41
• yes, but how prove $\lim x_n = \sqrt{\frac{a}{b}}$? – piteer Jul 13 '15 at 5:44
• Try and show that $x_n$ is eventually monotone, and bounded (depending on the value of $c$). Hence, the existence of the limit will follow from monotone convergence. – r9m Jul 13 '15 at 5:56
• @MichaelBurr just said how to compute the limit, if it exists. What remains is to prove that it exists. – Yves Daoust Jul 13 '15 at 5:58
• This is well-known Newton (or Babylonian) method – Michael Galuza Jul 13 '15 at 6:00

Let $v=\sqrt{\frac{a}{b}},b\gt0,x_1=c\gt 0$ Now we first show that $x_n^2\ge v$ for $n\ge2$,

since $x_n$ satisfied the quadratic equation $$x_n^2-2x_nx_{n+1}+v=0$$ this equation has a real root. Hence the discriminant $$4x_{n+1}^2-4v$$ must be non-negative, that is ,$x_{n+1}^2\ge v$ for $n\ge 1$

Now, $$x_n-x_{n+1}=x_n-\frac{1}{2}\left(x_n+\frac{v}{x_n}\right)=\frac{(x_n^2-v)}{2x_n}\ge0$$ $\implies x_{n+1}\le x_n$ for all $n\ge2$,
and as $x_{n}$ is both monotonically decreasing and bounded below, by Monotone-convergence-Theorem limit of the given sequence $x_n$ exists.

Take $\lim_{n\to \infty}x_n=l$, then $\lim_{n\to \infty}x_{n+1}=l$ and taking limit on both sides of the given expression, we have

$$l=\frac{l^2+\frac{a}{b}}{2l}$$ which gives ,

$$l^2=\frac{a}{b}$$ can you finish from here?

• He wants proof of existence of the limit... – pre-kidney Jul 13 '15 at 5:52
• @ pre-kidney: See ;) – Chiranjeev_Kumar Jul 13 '15 at 6:35

For convenience, let $s:=\sqrt{\dfrac ab}$.

Then,

$$\frac{x_{n+1}-s}{x_{n+1}+s}=\frac{\dfrac{x_n^2+s^2}{2x_n}-s}{\dfrac{x_n^2+s^2}{2x_n}+s}=\left(\frac{x_n-s}{x_n+s}\right)^2,$$

and by recurrence $$\frac{x_n-s}{x_n+s}=\left(\frac{c-s}{c+s}\right)^{2^n}.$$

This gives us the explicit formula

$$\color{green}{x_n=s\frac{1+r^{2^n}}{1-r^{2^n}}},$$

where $$r:=\frac{c-s}{c+s}.$$

It (quickly) converges to $s$ when $$|r|=\left|\frac{c-s}{c+s}\right|<1,$$ which is true for any $$c>0.$$

Choose the integer $k$ such that $2^k\le s^2<2^{k+1}$ ($k$ is the rank of the most significant bit in $s^2$) and let $$c=\frac1{\sqrt2}\cdot2^{k/2}\text{ or }c=\sqrt2\cdot2^{(k-1)/2}$$ depending on the parity of $k$. Then $$\frac 1{\sqrt2}\le\frac cs<\sqrt2.$$

This makes an excellent starting approximation, as at worse $r=0.086427\cdots=2^{-3.5323\cdots}$ and the iterates give at least $3.5,7,28,56\cdots$ exact bits, which are enough for the single and double precision floating-point representations.

Let $r=\frac{a}{b}$ and assume that $r>0$ and $c>0$. To prove existence of the limit, rewrite the equation as follows: $$2x_{n+1}=x_n + \frac{r}{x_n}\quad (\star)$$ Since $x_1=c>0$ and $r>0$, it follows by induction that all $x_n$ are positive. Applying the AM-GM Inequality, we see that $x_{n+1}\geq \sqrt{r}$ (for $n\geq 1$). Squaring both sides of $(\star)$ yields \begin{align*} 4x_{n+1}^2&=x_n^2 + 2r + \frac{r^2}{x_n^2}\\ \implies 4x_{n+1}^2-4r&=\left(x_n-\frac{r}{x_n}\right)^2\\ \implies \left|\frac{x_{n+1}^2-r}{x_n^2-r}\right|&=\frac{\left|1-\frac{r}{x_n^2}\right|}{4}. \end{align*}

Since $x_n\geq \sqrt{r}$ for $n\geq 2$, it follows that $\left|1-\frac{r}{x_n^2}\right|\leq 1$ for $n\geq 2$. Consequently $$\left|x_{n+1}^2-r\right|\leq \left(\frac{1}{4}\right)\cdots \left(\frac{1}{4}\right)\left(\frac{\left|1-\frac{r}{c^2}\right|}{4}\right)\left|c^2-r\right|=\frac{C}{4^n},$$ for some positive constant $C$.

Taking the limit as $n\to\infty$, it follows that $\lim_{n\to\infty} x_{n+1}^2=r$, and therefore $\lim_{n\to\infty}x_n=\sqrt{r}$ as desired.

• How do you know that $|1-r/x^2_n| < 1$? $x_n$ might be very small compared to $r$, so $1-r/x^2_n < 0$ and large in absolute value. – marty cohen Jul 13 '15 at 6:13
• In fact, $x_n^2 \geq r$ by AM-GM, which ensures that $1-r/x_n^2\geq 0$. I will include this argument, good catch! – pre-kidney Jul 13 '15 at 6:16
• What if $x_1 = r/1000$? – marty cohen Jul 13 '15 at 6:20
• No problem; simply start telescoping from $n=2$. See the edits... – pre-kidney Jul 13 '15 at 6:27
• OK. btw, $x+r/x = x-2\sqrt{r}+r/x + 2\sqrt{r} = (\sqrt{x}-\sqrt{r/x})^2+2\sqrt{r} \ge 2\sqrt{r}$, so you don't need to invoke am-gm. – marty cohen Jul 13 '15 at 6:53

Let $L =\sqrt{\dfrac{a}{b}}$, then $x_{n+1}-x_n = \dfrac{x_n^2+L^2}{2x_n}-x_n=\dfrac{L^2-x_n^2}{2Lx_n}\leq 0$ because $L \leq x_n$ is true by AM-GM inequality: $x_n^2+L^2 \geq 2Lx_n\to x_{n+1} = \dfrac{x_n^2+L^2}{2x_n} \geq L, \forall n \geq 1$, and $x_n \geq L$ so it is decreasing and bounded below by $L$, hence converges also to $L$. The "also" part needs some more clarification: $l = \displaystyle \lim_{n\to \infty} x_n$, then $l = \dfrac{l^2+L^2}{2l}\to l^2=L^2 \to l = L$

• This argument proves that the limit exists and that the limit is greater than or equal to $L$, but does not rule out the possibility that it is strictly larger than $L$. – pre-kidney Jul 13 '15 at 6:05
• For example, the sequence $\frac{n+1}{n}$ is decreasing and bounded below by $0$, but converges to $1$. – pre-kidney Jul 13 '15 at 6:06