# induction

• August 24th 2009, 03:59 PM
justchillin
induction

Suppose that $R > 0$, $x_{0}>0$, and
$x_{n+1}= \frac{1}{2}(\frac{R}{x_{n}}+x_{n})$, $n\geq0$

Prove: For $n\geq1$, $x_{n}>x_{n+1}>\sqrt{R}$ and
$x_{n}-\sqrt{R}\leq\frac{1}{2^n}\frac{(x_{o}-\sqrt{R})^2}{x_{o}}$

MY attempt at a solution:

I really don't know how to go about this... at first i tried to show that if $x_{n}>x_{n+1}>\sqrt{R}$ is true then $x_{n}-x_{n+1} > 0$.

So that means
$x_{0}- \frac{1}{2}(\frac{R}{x_{0}}+x_{0})>0$
$\frac{x_{0}}{2}-\frac{R}{2x_{0}}>0$
$x_{0}-\frac{R}{x_{0}}>0$

My problem is that i don't know how big R in comparison to $x_{0}$, so unless i restrict R to be less than $x_{0}$ i can't prove that $x_{n}>x_{n+1}>\sqrt{R}$

Basically, i need help with this question... can anyone help ?

I'm doing a self study by myself so i would appreciate a detailed solution if possible.. please and thank u.
• August 24th 2009, 06:27 PM
Enrique2
I believe you are right, in fact if $x_0<\sqrt{2}$ (for
instance $x_0=1$ and $R=4$ then the sequence increases in the first terms $x_1>x_0$, but $x_1>x_2>2$ and then the hypothesis seems to hold (for
$n\geq 1$ as stated).

However, if $x_0=\sqrt{R}$ we have the constant sequence $(\sqrt{R})$

I conjecture without doing any more calculations that this is the unique problem with the hypothesis, we have to require $x_0\neq \sqrt{R}$.

I suggest
a) Try to prove the inequality if $x_0>\sqrt{R}$, it seems an easy induction at least for the first one.
b) Try to show using differential calculus that $f(x):=\frac{1}{2}\left(\frac{R}{x}+x\right)$
maps $[0,\sqrt{R})$ into $(\sqrt{R},\infty)$. This would solve the case fos "small $x_0$'s"
because it would allow to apply a)
I haven't made the calculations but it seems to me the way of attacking it.
• August 25th 2009, 04:21 AM
justchillin
Sorry i'm not very sure about what you're asking me to do.

My point was that $x_{n}>x_{n+1}$ is not true for all n if R> $x_{0}$. So do i restrict R so that this case is satistfied ?

If i do this then it would seem that the sequence is decreasing at first but then it would blow up to infinity .

The question is puzzuling to me.
• August 25th 2009, 05:34 AM
Enrique2
My idea is to divide the problem in the following cases:

a) If $x_0>\sqrt{R}$ then $x_0>x_1>\cdots x_n >\sqrt{R}$ and the sequence tends to $\sqrt{R}$. I believe it follows from the inequality you obtained in the first post, by an easy induction. Observe that the inequality you got is $x_0-x_1=\frac{x_0^2-R}{2x_0}$. If $x_0>\sqrt{R}$ then you have clearly $x_0>x_1>\sqrt{R}$ and you can apply induction. For showing $x_1>\sqrt{R}$ you have to use that $f(x):=\frac{1}{2}\left(\frac{R}{x}+x\right)$ is increasing in $[\sqrt{R},\infty)$ and $f(\sqrt{R})=\sqrt{R}$.

b) If $x_0=\sqrt{R}$ then $x_n=\sqrt{R}$ for all $n$.

c) If $x_0<\sqrt{R}$ then $x_1>\sqrt{R}>x_0$ and then $x_1>x_2>\cdots x_n >\sqrt{R}$ by the same argument of a). The key for obtaining $x_1>\sqrt{R}$ is to observe that
$f(x):=\frac{1}{2}\left(\frac{R}{x}+x\right)$ is decreasing in $(0,\sqrt{R}]$ and $f(\sqrt{R})=\sqrt{R}$.

I mean that $f(x):=\frac{1}{2}\left(\frac{R}{x}+x\right)$, $x\in \mathbb{R}^+$ has a unique attracting point , the minimum, and that any iteration goes to this point. The case b)
is an exception to your statement since it involves strict inequalities. c) is NOT an exception since you have to show $x_n>x_{n+1}>\sqrt{R}$ for $n\geq 1$,

If it is still not clear I will try to write any step detailedly, but I don't have now the necessary time.