# Let $x_{n+1} = \frac{1}{2}(x_n + \frac{a}{x_n})$. Prove that $x_{n+1} < x_{n}$

Let $$x_{n+1} = \frac{1}{2}(x_{n} + \frac{a}{x_{n}})$$

Prove that $$x_{n+1} < x_{n}$$ for $$a \geq 0$$.

Hint: Let the initial guess satisfy $$x_{1} > \sqrt{a}$$

I am stuck at how to begin this. I would like to use an induction proof, but there is no simple way for me to relate the base case and begin. That is I can't even establish: $$x_{2} < x_{1}$$

How would I do this since there is no given initial term? Or is that a mistake and an initial term should be present?

• To show that $x_2<x_1,$ we have $$x_2=\frac{1}{2}\left(x_1+\frac{a}{x_1}\right)<\frac{1}{2}\left(x_1+\frac{x_1^2}{x_1}\right)=x_1.$$ – cmk May 22 at 1:06

Lemma: $$x_n>\sqrt{a}$$ for all $$n\ge 1$$.

Proof: The proof is by induction. Suppose $$x_n>\sqrt{a}$$. Divding $$a$$ by both sides, you get $$\frac{a}{x_n}<\sqrt{a}$$. Combining these, you get $$x_n>\frac a{x_n}$$, so $$\sqrt{x_n}>\sqrt{\frac a{x_n}}$$, so $$\left(\sqrt{x_n}-\sqrt{\frac a{x_n}}\right)^2>0$$ This rearranges to $$\frac12\left(x_n+\frac{a}{x_n}\right)>\sqrt{a}$$ which is exactly $$x_{n+1}>\sqrt{a}$$. $$\hspace{.2cm}\square$$

Now we know $$x_n>\sqrt{a}$$ for all $$n$$, which as before implies $$x_n>\frac{a}{x_n}$$. Conclude with $$x_{n}=\frac12 x_n+\frac12 x_n> \frac12 x_n+\frac12\cdot \frac{a}{x_{n}}=x_{n+1}$$

• This is a slick proof.....What was your thought process to use the relation $\frac{a}{x_n} < \sqrt{a}$? I'm really trying to improve my perceptive skills and without looking at this I would never had thought of this idea.... – dc3rd May 22 at 2:07
• @dc3rd My solution obscured the intuition. The insight is from the AM GM inequality; since $x_{n+1}$ is the (arithmetic) average of $x_n$ and $a/x_n$, it follows it is at least the geometric average of these two, which is exactly $\sqrt a$. Now you have $x_{n+1}$ is the average of two numbers, one is $x_n$, and the other is at most than $x_n$. Replacing “at most” with “strictly less than,” however, requires careful reasoning. – Mike Earnest May 22 at 3:16

Hint: $$x_n- x_{n+1}=x_n-\frac{1}{2}\left(x_n+\frac{a}{x_n}\right)=\frac{1}{2} \frac{x_n^2-a}{x_n} \geq 0$$ since $$x_n^2 \geq a$$ (?)

• Since $x^{2}_{n} \geq a$ then $x_{n} \geq \sqrt{a}$. Then that would be enough to establish the expression??? – dc3rd May 22 at 1:14
• I dont understand what you are saying. Once you have proved $x_n^2 \geq a$ then from the mentioned expression, $x_n$ decreases – Chinnapparaj R May 22 at 1:30
• What I was asking was precisely that. That once we show this difference is positive we can conclude that $x_{n}$ decreases? – dc3rd May 22 at 1:36
• Yea! Right!.... – Chinnapparaj R May 22 at 1:37

I suppose $$a>0$$. Now consider the function $$f(x)=\frac12\left(x+\frac{a}{x}\right)$$ for $$x>\sqrt{a}$$. Take the derivative and show that the derivative is positive then deduce that the function is an increasing one. After that start an induction. If $$x_n>x_{n+1}$$ then $$f(x_n)>f(...$$

Sine x1 > √a, it is a positive value, then we will have for x2:

$$x2 = \frac{1}{2}(x1 + \frac{a}{x1}) = \frac{1}{2}\frac{(x1^2+a)}{x1}$$

Now in order to compare them we have:

$$\frac{1}{2}\frac{(x1^2+a)}{x1}$$

VS $$x1$$

Since x1 is at least √a, we substitute it in the formulas:

$$\frac{1}{2}\frac{(a^++a)}{√a^+}$$

VS $$√a^+$$

Multiplying by 2√a^+ gives us:

$$(a^++a)$$

VS $$2a^+$$

Obviously, the second side, x1 is bigger than x2.

For the rest, you might need to use induction approach.

$$x_{n+1} = \frac{1}{2}(x_{n} + \frac{a}{x_{n}})$$ so $$x_{n+1}^2 = \frac14(x_{n}^2+2a + \frac{a^2}{x_{n}^2})$$ so $$x_{n+1}^2-a = \frac14(x_{n}^2+2a + \frac{a^2}{x_{n}^2})-a = \frac14(x_{n}^2-2a + \frac{a^2}{x_{n}^2}) = \frac14(x_{n}-\frac{a}{x_{n}})^2$$.

Therefore $$x_{n+1}^2 \ge a$$.

Now we can compare $$x_{n+1}$$ and $$x_m$$.

$$x_{n+1}^2-x_n^2 = \frac14(-3x_{n}^2+2a + \frac{a^2}{x_{n}^2}) = -\frac14(3x_{n}^2-2a - \frac{a^2}{x_{n}^2})$$. Since, for $$n \ge 2$$, $$x_n^2 \ge a$$, $$\frac{a^2}{x_{n}^2} \le a$$ so $$2a + \frac{a^2}{x_{n}^2} \le 3a \le 3x_n^2$$ so $$3x_{n}^2-2a - \frac{a^2}{x_{n}^2} \ge 0$$ so $$x_{n+1}^2-x_n^2 \le 0$$ so $$x_{n+1} \le x_n$$.

Assuming $$a>0$$ and starting value $$x_0> 0$$, just apply AM-GM directly:

• $$\frac{1}{2}\left(x +\frac{a}{x}\right) \geq \sqrt{x\cdot \frac{a}{x}}= \sqrt{a}$$ with equality if and only if $$x=\frac{a}{x} \Leftrightarrow x=\sqrt{a}$$

We conclude for $$x_0 = \sqrt{a}$$ you get the constant sequence $$x_n = \sqrt{a}$$, otherwise for any $$x_0>0, x_0 \neq \sqrt{a}$$ you have $$x_1 > \sqrt{a}$$ and, hence $$x_n > \sqrt{a}$$ for $$n\geq 1$$.

If follows immediately

$$\color{blue}{x_n - x_{n+1}} = x_n - \frac{1}{2}\left(x_n +\frac{a}{x_n}\right)= \frac{1}{2}\left(x_n -\frac{a}{x_n}\right) \stackrel{x_n > \sqrt{a}}{\color{blue}{>}} \frac{1}{2}\left(\sqrt{a} -\frac{a}{\sqrt{a}}\right)= \color{blue}{0}$$

• A little simpler if you write that 3rd expression as $\frac{x_n^2-a}{2x_n} > 0$ since $x_n > \sqrt{a}$. – marty cohen May 25 at 4:00
• @martycohen Interesting how different the perception of "simpler" is. To me $\frac{1}{2}\left(x_n -\frac{a}{x_n}\right)$ looked simpler as the following inequality is just adding the two inequalities $x_n > \sqrt{a}$ and $-\frac{a}{x_{n}} > -\frac{a}{\sqrt{a}}$. :-) – trancelocation May 25 at 4:08

If you rewrite $$x_{n+1} = \frac{1}{2}\left(x_{n} + \frac{a}{x_{n}}\right)$$ as $$x_{n+1} =x_n-\frac{x_n^2-a}{2x_{n}}$$ you recognize the iteration scheme of Newton method for finding the zero of function $$f(x)=x^2-a$$ the second derivative is $$f''(x)=2$$. So, by Darboux theorem, if you start with any $$x_0$$ such that $$f(x_0)\times f''(0)$$ (which, in your case, reduces to $$f(x_0) >0$$ that is to say $$x_0 > \sqrt a$$), you will never overshoot the solution which means that you will approach $$\sqrt a$$ by decreasing values. Otherwise, that is to say if you start with $$x_0 < \sqrt a$$, by the same theorem, you are sure to overshoot once the solution.

For illustration purposes, let us use $$a=123456789$$ and use $$x_0=15000$$; this will give as iterates $$\left( \begin{array}{cc} n & x_n \\ 0 & 15000.000000000000000 \\ 1 & 11615.226300000000000 \\ 2 & 11122.050674131578909 \\ 3 & 11111.116440640069489 \\ 4 & 11111.111060556857979 \\ 5 & 11111.111060555555441 \end{array} \right)$$

while starting with $$x_0=10000$$ (which is much closer to the solution) we should get $$\left( \begin{array}{cc} n & x_n \\ 0 & 10000.000000000000000 \\ 1 & \color{red}{11172.839450000000000} \\ 2 & 11111.281580953725353 \\ 3 & 11111.111061864009645 \\ 4 & 11111.111060555555441 \end{array} \right)$$