Prove $ \lim\limits_{x\to\infty}y_{n}=\sqrt{x}$ if $y_{n}=\frac{1}{2}\left(y_{n-1}+\frac{x}{y_{n-1}}\right),n\in \mathbb{N},x>0,y_{0}>0$

Question

Can someone say how to solve this problem? In solution, it says that it stars with $$\frac{y_{n}-\sqrt{x}}{y_{n}+\sqrt{x}}=\left(\frac{y_{n-1}-\sqrt{x}}{y_{n-1}+\sqrt{x}}\right)^2,n\ge 1$$ How to get to this formula?

Answer 1

We have that

$$y_n=\frac12\left(y_{n-1}+\frac{x}{y_{n-1}}\right)\implies y_{n-1}^2-2y_ny_{n-1}+2x=0 \tag 1$$

Now, multiplying $(1)$ by $x^{1/2}$ yields the following obvious identity

$$y_{n-1}^2\sqrt{x}-2y_ny_{n-1}\sqrt{x}+2x\sqrt{x}=-(y_{n-1}^2\sqrt{x}-2y_ny_{n-1}\sqrt{x}+2x\sqrt{x}) \tag 2$$

Next, adding $y_ny_{n-1}^2+xy_n-2xy_{n-1}$ to both sides of $(2)$ reveals

$$\begin{align} &y_ny_{n-1}^2+xy_n-2xy_{n-1}+y_{n-1}^2\sqrt{x}-2y_ny_{n-1}\sqrt{x}+2x\sqrt{x}\\\\ &=y_ny_{n-1}^2+xy_n-2xy_{n-1}-(y_{n-1}^2\sqrt{x}-2y_ny_{n-1}\sqrt{x}+2x\sqrt{x}) \tag 3 \end{align}$$

Factoring both sides of $(3)$ we have

$$(y_n-\sqrt{x})(y_{n-1}+\sqrt{x})^2=(y_n+\sqrt{x})(y_{n-1}-\sqrt{x})^2 \tag 4$$

whereupon rearranging $(4)$ gives the coveted identity

$$\frac{y_n-\sqrt{x}}{y_n+\sqrt{x}}=\left(\frac{y_{n-1}-\sqrt{x}}{y_{n-1}+\sqrt{x}}\right)^2$$

---

It is easy to see that the sequence

$$\phi_n\equiv \frac{y_n-\sqrt{x}}{y_n+\sqrt{x}}$$

converges since we have $\phi_n=\phi_{n-1}^2$ and $\phi_n<1$ for all $n$.

Thus, $\phi_n \to 0$ and thus $y_n\to \sqrt{x}$ as was to be shown!

Answer 2

The function $y \to 1/2(y+ x/x)$ is continous for $y > 0$. So the limit of your sequence can only be $\sqrt{x}$, i.e. the positive root of $y=f(y)$.

Then you should study the monotonicy of $(y_n)$.

Your sequence is an example of the Newton's method applied to the function $y \to y-x^2$.

Answer 3

You can use this way to get the formula. Note \begin{eqnarray} y_n-\sqrt{x}&=&\frac12\left(y_{n-1}-2\sqrt{x}+\frac{x}{y_{n-1}}\right)\\ &=&\frac12\left(\sqrt{y_{n-1}}-\frac{\sqrt{x}}{\sqrt{y_{n-1}}}\right)^2\\ &=&\frac12\left(\frac{y_{n-1}-\sqrt{x}}{\sqrt{y_{n-1}}}\right)^2. \end{eqnarray} Similary \begin{eqnarray} y_n+\sqrt{x}=\frac12\left(\frac{y_{n-1}+\sqrt{x}}{\sqrt{y_{n-1}}}\right)^2. \end{eqnarray} Now I think you can get the answer.

Answer 4

The desired formula comes directly from the definitions. \begin{align} \frac{y_{n} - \sqrt{x}}{y_{n} + \sqrt{x}} &= \dfrac{\dfrac{1}{2}\left(y_{n - 1} + \dfrac{x}{y_{n - 1}}\right) - \sqrt{x}}{\dfrac{1}{2}\left(y_{n - 1} + \dfrac{x}{y_{n - 1}}\right) + \sqrt{x}}\notag\\ &= \dfrac{y_{n - 1}^{2} + x - 2y_{n - 1}\sqrt{x}}{y_{n - 1}^{2} + x + 2y_{n - 1}\sqrt{x}}\notag\\ &= \left(\frac{y_{n - 1} - \sqrt{x}}{y_{n - 1} + \sqrt{x}}\right)^{2}\tag{1} \end{align} Using this recursive formula you get $$\frac{y_{n} - \sqrt{x}}{y_{n} + \sqrt{x}} = \left(\frac{y_{0} - \sqrt{x}}{y_{0} + \sqrt{x}}\right)^{2^{n}} = k^{2^{n}}$$ where the constant $k = (y_{0} - \sqrt{x})/(y_{0} + \sqrt{x}) < 1$. And since $2^{n} > n$ it follows that $k^{2^{n}} < k^{n}$ therefore we have $$0 < \frac{y_{n} - \sqrt{x}}{y_{n} + \sqrt{x}} < k^{n}\tag{2}$$ for all $n$. Noting that $k^{n} \to 0$ as $n \to \infty$ we can see that $y_{n} \to \sqrt{x}$.

There are two fine points to note in the whole argument. We have assumed that $y_{0} > \sqrt{x}$ which makes $k$ positive. If this was not the case the relation $$\frac{y_{1} - \sqrt{x}}{y_{1} + \sqrt{x}} = \left(\frac{y_{0} - \sqrt{x}}{y_{0} + \sqrt{x}}\right)^{2}$$ ensures that $y_{1} > \sqrt{x}$ and hence we can apply the recursion $(1)$ only till $y_{1}$ and continue the argument.

Another point to note is that the part $y_{n} + \sqrt{x}$ is denominator is bounded. This is essential to get the conclusion $y_{n} \to \sqrt{x}$ from equation $(2)$. To establish this we need to know that $y_{n - 1} > \sqrt{x}$ for all $n \geq 2$ and hence $$y_{n} - y_{n - 1} = \frac{x - y_{n - 1}^{2}}{2y_{n - 1}} < 0$$ so that $y_{n}$ is decreasing and hence $0 < \sqrt{x} < y_{n} < y_{1}$ for all $n$. This shows that $y_{n} + \sqrt{x}$ lies between $\sqrt{x}$ and $y_{0} + \sqrt{x}$ and is hence bounded.

---

The second point above brings us to a much simpler proof. Sequence $y_{n}$ is decreasing and $y_{n} > \sqrt{x}$, it follows that $y_{n}$ tends to some limit $L \geq \sqrt{x} > 0$. And $y_{n - 1} \to L$ also. The equation $$y_{n} = \frac{1}{2}\left(y_{n - 1} + \frac{x}{y_{n - 1}}\right)$$ now tells us that $$L = \frac{1}{2}\left(L + \frac{x}{L}\right)$$ or $L^{2} = x$. Since $L > 0$ it follows that $L = \sqrt{x}$. This proof does not need the use of complicated formula $(1)$.