# Convergence of $x_{n+1} = \frac12(x_n + \frac2{x_n}).$ [duplicate]

Let $x_1=1$ and $$x_{n+1} = \frac12\left(x_n + \frac2{x_n}\right).$$ Prove or disprove $(x_n)$ is convergent and show the limit.

When I tried working on it I found the sequence was bounded by square root of 2 and it is was monotone. But apparently the sequence is not bounded by square root of two and is not monotone. But I have no idea why. Any help would be greatly appreciated! Thanks!

• The sequence is bounded by $\sqrt{2}$ and is monotone. – njguliyev Nov 2 '13 at 21:10
• $x_2 = 1.5$, so it isn't bounded by $\sqrt{2}$. However, for $n \ge 2$, it is monotone in the other direction, and bounded below by $\sqrt 2$. It is the Newton-Raphson method for solving $x^2-2 = 0$, and if you look at the beginning of the movie "21" you will be able to deduce a picture proof. – Stephen Montgomery-Smith Nov 2 '13 at 21:14
• You guys were all correct! I was originally right but was looking at the problem at a more complex angle. – monkeyman Nov 18 '13 at 22:54

Let $y_n = x_{n}^2$, then \begin{align*} \\y_{n+1} = x_{n+1}^2 &= \frac{1}{4}\left(x_n + \frac2{x_n}\right)^2 \\ &=\left(\frac{x_n}{2}\right)^2 +\left(\frac{1}{x_n}\right)^2 + 1 \ge 2\sqrt{\frac{x_n}{2}\cdot\frac{1}{x_n}} +1 = \sqrt{2}+1 \gt 2 \tag{1} \end{align*} Thus by (1), we have $x_n \gt \sqrt{2}~~(n\ge 2)$. Also, by the given condition, we have: $$x_{n+1}-x_n=\frac{1}{2}x_n+\frac{1}{x_n}-x_n=\frac{1}{x_n}-\frac{x_n}{2} \tag{2}$$ (2) implies that the sequence is decreasing when $x_n \gt \sqrt{2}$ and we have already known that for $n \ge 2$, $x_n \gt \sqrt{2}$. So $x_n$ is decrease and bound below by $\sqrt{2}$. Hence, $x_n$ is convergent.

Note: Let $f(x) = \frac{1}{x} +\frac{x}{2}$, then $$f(x)\ge 0 \space\text{when } x \in (-\infty,-\sqrt2] \cup (0,\sqrt2]$$ $$f(x)\lt 0 \space\text{when } x \in (-\sqrt2,0) \cup (\sqrt2, +\infty)$$

$$x_{n+1}-x_n=\frac{1}{2}x_n+\frac{1}{x_n}-x_n=\frac{1}{x_n}-\frac{x_n}{2}$$

$$\text{(x_n)bounded above by \sqrt{2} iff (x_n) is monotonically increasing??}$$

$$\text{Does this reduce your problem to check only for one of monotonicity/ boundedness?}$$

You can use the contraction mapping theorem that says:

If $T:X\rightarrow X$ is a contraction mapping on a complete metric space $(X,d)$ then there is exactly one solution $x\in X$ of $T(x) = x$.

Denote $x_{n+1} = Tx_n$. You can then show that $T$ is a contraction with $Tx = \frac{1}{2}(x+\frac{a}{x})$. For $x_1, x_2> 0$ we estimate that $$|Tx_1-Tx_2| = \bigg |\frac{1}{2}(x_1+a/x_1-\frac{1}{2}(x_2+a/x_2)\bigg | = \frac{1}{2}\bigg |1-\frac{a}{x_1 x_2} \bigg | |x_1-x_2|.$$ So we want $\frac{1}{2}\bigg |1-\frac{a}{x_1 x_2}\bigg |<1$ To be a contraction. T contracts when $3x_1 x_2>a$. We want to exclude arguments of $x$ small. Consider the action of $T$ on an interval of the form $[b,\infty)$ with $b>0$. This is a complete metric space because $[b,\infty)$ is a closed subset of $\mathbb{R}$ and $\mathbb{R}$ is complete. To make a choice for $b$ observe that $$Tx = \sqrt{a}+\dfrac{(x-a)^2}{2x}\geq \sqrt{a}$$ for all $x>0$. Therefore the restriction of $T$ to $[\sqrt{a},\infty)$ is well-defined since $T([\sqrt{a},\infty))\subset [\sqrt{a},\infty)$ and $T$ is a contraction on $[\sqrt{a},\infty)$ with $c=\frac{1}{2}$. It follows for any $x_0\geq\sqrt{a}$ the sequence $x_n = T^nx_0$ converges to $\sqrt{a}$ as $n\rightarrow\infty$. In your case $a=2$.

I find it interesting that this is more easily answered by looking at $x_n^2$ instead of $x_n$.

From $x_{n+1} = \frac12\left(x_n + \frac2{x_n}\right)$, $x_{n+1}^2 = \frac14\left(x_n^2+4+\frac{4}{x_n^2}\right)$, so $x_{n+1}^2-2 = \frac14\left(x_n^2-4+\frac{4}{x_n^2}\right) = \frac14\left(x_n - \frac2{x_n}\right)^2 = \frac14\left(\frac{x_n^2 - 2}{x_n}\right)^2 = \left(\frac{x_n^2 - 2}{2x_n}\right)^2$.

Once $x_n > \frac12$ and $|x^2_n-2| < 1$, this implies quadratic convergence.

Note: As in many of my answers, there is absolutely nothing original here.

From an algebraic point of view, you can rewrite your equation as
$X_{n+1} = X_n - (X_n^2 - 2) / (2 X_n)$ This corresponds to the Newton scheme for solving $f(X) = X^2 - 2 = 0$

let $a,b$ be t wo arbitrary numbers and for every $n \geq 1\in \mathbb{N}$ : $$x_1=b$$ $$x_{n+1}=\dfrac12\left(x_n+\dfrac{a}{x_n} \right)$$

We want to prove that this sequence converges to $\sqrt{a}$ .

we have :

$$h+\dfrac{1}{h}\geq2 \ \ \ : \ \ \ \forall \ \ h>0$$

So :

$$x_{n+1}=\dfrac12\left(x_n+\dfrac{a}{x_n} \right)=\dfrac{\sqrt{a}}{2}\left(\dfrac{x_n}{\sqrt{a}}+\dfrac{\sqrt{a}}{x_n} \right)\geq \dfrac{\sqrt{a}}{2}\cdot2\geq2$$

$$x_n\geq2 \ \ \ : \ \ \ \forall \ \ n\geq2$$

Now :

$$\dfrac{x_{n+1}}{x_n}=\dfrac12\left(1+\dfrac{a}{x_n} \right)\leq\dfrac12\left(1+\dfrac{a}{(\sqrt{a})^2} \right)=1$$

Thus the sequence $(x_n)$ is decreasing and bounded below and thus it is convergent .

let $l:=\lim\limits_{n}x_n$ then we have :

$$\lim\limits_{n}x_{n+1}=\lim\limits_{n}\dfrac12\left(x_n+\dfrac{a}{x_n} \right)=\dfrac12\left(l+\dfrac{a}{l}\right) \Rightarrow \lim\limits_{n}x_{n}=\sqrt{a}$$