5
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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.$$ $\endgroup$
    – cmk
    May 22, 2019 at 1:06

7 Answers 7

Reset to default
4
$\begingroup$

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$ (?)

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

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} $$

$\endgroup$
2
  • $\begingroup$ 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.... $\endgroup$
    – D.C. the III
    May 22, 2019 at 2:07
  • 3
    $\begingroup$ @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. $\endgroup$
    – Mike Earnest
    May 22, 2019 at 3:16
2
$\begingroup$

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(...$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

$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$.

$\endgroup$
1
$\begingroup$

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}$$

$\endgroup$
2
  • $\begingroup$ A little simpler if you write that 3rd expression as $\frac{x_n^2-a}{2x_n} > 0$ since $x_n > \sqrt{a}$. $\endgroup$
    – marty cohen
    May 25, 2019 at 4:00
  • $\begingroup$ @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}}$. :-) $\endgroup$
    – trancelocation
    May 25, 2019 at 4:08
0
$\begingroup$

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)$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .