4
$\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$
  • $\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 at 1:06
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$
  • $\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$ – dc3rd May 22 at 2:07
  • 2
    $\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 at 3:16
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$
  • $\begingroup$ Since $x^{2}_{n} \geq a$ then $x_{n} \geq \sqrt{a}$. Then that would be enough to establish the expression??? $\endgroup$ – dc3rd May 22 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 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$ – dc3rd May 22 at 1:36
  • $\begingroup$ Yea! Right!.... $\endgroup$ – Chinnapparaj R May 22 at 1:37
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$
  • $\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 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 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.