Problem 1167

Let $\sqrt{a}=x$, thus $a=x^{2}$.

1.) To prove: If $0<x$, then $u_{0} x-\Delta x$ with $x>\Delta x>0$ (by assumption). Then,

$$u_{1}=\frac{1}{2}\left(u_{0}+\frac{a}{u_{0}}\right)=\left(x-\Delta x+\frac{x^{2}}{x-\Delta x}\right)=x+\frac{\Delta x^{2}}{2(x-\Delta x)}$$

Since $x>\Delta x$, it follows that $x-\Delta x>0$, and thus

$$\frac{\Delta x^{2}}{2(x-\Delta x)}>0$$

and therefore $u_{1}>x=\sqrt{a}$.

2.) To prove: If $u_{n}>x$, then $u_{n+1}=\frac{1}{2}\left(u_{n}+\frac{a}{u_{n}}\right)>x$.

Proof: Let $u_{n}=x+\Delta x$ with $\Delta x>0$ (by assumption). Then,

$$u_{n+1}=\frac{1}{2}\left(u_{n}+\frac{a}{u_{n}}\right)=\left(x+\Delta x+\frac{x^{2}}{x+\Delta x}\right)=x+\frac{\Delta x^{2}}{2(x+\Delta x)}$$

Now,

$$0<\frac{\Delta x^{2}}{2(x+\Delta x)} \quad \text{(since $\Delta x>0$, $\frac{x}{\Delta x}>0$)}, \text{ thus}$$

$$u_{n}=x+\Delta x>u_{n+1}=x+\frac{\Delta x^{2}}{2(x+\Delta x)}>x=\sqrt{a}$$

3.) With these proofs, it is shown that the sequence $\left\{u_{n}\right\}$ approaches $\sqrt{a}=x$ (at least from the second term onwards from above), but it is not yet proven that it actually converges to this value (i.e., that it approaches it arbitrarily closely). It could be that it converges to a value $x+c$, where $c$ is a positive constant.

If $u_{n}=x+\Delta x_{n}$ (so $\Delta x_{n}>0$), then

$$u_{n+1}=\frac{1}{2}\left(x+\Delta x_{n}+\frac{x^{2}}{x+\Delta x_{n}}\right)=x+\frac{\Delta x_{n}^{2}}{2\left(x+\Delta x_{n}\right)}=x+\Delta x_{n+1}$$

Now,

$$0<\Delta x_{n+1}=\frac{\Delta x_{n}^{2}}{2(x+\Delta x_{n})}<\frac{\Delta x_{n}^{2}}{2x}<\frac{\Delta x_{n}}{2} \quad \text{(since $x>\Delta x_{n}$ and $\Delta x_{n}>0$)}$$

Thus, $\Delta x_{n+1}<\frac{\Delta x_{n}}{2}$, and by induction, $\Delta x_{n}<\frac{\Delta x_{1}}{2^{n-1}}$ for all $n \geq 1$. Therefore, the sequence $\left\{\Delta x_{n}\right\}$ is decreasing and bounded below by 0, so it converges to 0.

Consider the sequence $\left\{v_{n}\right\}=\left\{x+\frac{\Delta x_{1}}{2^{n-1}}\right\}$. This is a majorant for the sequence $\left\{u_{n}\right\}$. Since

$$\lim _{n \rightarrow \infty} v_{n}=\lim _{n \rightarrow \infty}\left(x+\frac{\Delta x_{1}}{2^{n-1}}\right)=x$$

and $u_{n}>x$ for every $n$, by the majorant criterion, it follows that $\lim _{n \rightarrow \infty} u_{n}=x=\sqrt{a}$.

Conclusion: For every $a>0$ and for every $\Delta x_{0}>0$, the sequence $\left\{u_{n}\right\}$ with $u_{n+1}=\frac{1}{2}\left(u_{n}+\frac{a}{u_{n}}\right)$ converges to $\sqrt{a}$.

Thus, one can start from any initial approximation (even seemingly nonsensical ones like $\sqrt{a} \approx 1$ or $\sqrt{a} \approx a$). The approximation will approach the correct value from above, at the latest from the second term onwards.