# induction

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

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

Prove: For $\displaystyle n\geq1$, $\displaystyle x_{n}>x_{n+1}>\sqrt{R}$ and
$\displaystyle 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 $\displaystyle x_{n}>x_{n+1}>\sqrt{R}$ is true then $\displaystyle x_{n}-x_{n+1} > 0$.

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

My problem is that i don't know how big R in comparison to $\displaystyle x_{0}$, so unless i restrict R to be less than $\displaystyle x_{0}$ i can't prove that $\displaystyle 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.
• Aug 24th 2009, 06:27 PM
Enrique2
I believe you are right, in fact if $\displaystyle x_0<\sqrt{2}$ (for
instance $\displaystyle x_0=1$ and $\displaystyle R=4$ then the sequence increases in the first terms $\displaystyle x_1>x_0$, but $\displaystyle x_1>x_2>2$ and then the hypothesis seems to hold (for
$\displaystyle n\geq 1$ as stated).

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

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

I suggest
a) Try to prove the inequality if $\displaystyle x_0>\sqrt{R}$, it seems an easy induction at least for the first one.
b) Try to show using differential calculus that $\displaystyle f(x):=\frac{1}{2}\left(\frac{R}{x}+x\right)$
maps $\displaystyle [0,\sqrt{R})$ into $\displaystyle (\sqrt{R},\infty)$. This would solve the case fos "small $\displaystyle 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.
• Aug 25th 2009, 04:21 AM
justchillin
Sorry i'm not very sure about what you're asking me to do.

My point was that $\displaystyle x_{n}>x_{n+1}$ is not true for all n if R> $\displaystyle 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.
• Aug 25th 2009, 05:34 AM
Enrique2
My idea is to divide the problem in the following cases:

a) If $\displaystyle x_0>\sqrt{R}$ then $\displaystyle x_0>x_1>\cdots x_n >\sqrt{R}$ and the sequence tends to $\displaystyle \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 $\displaystyle x_0-x_1=\frac{x_0^2-R}{2x_0}$. If $\displaystyle x_0>\sqrt{R}$ then you have clearly $\displaystyle x_0>x_1>\sqrt{R}$ and you can apply induction. For showing $\displaystyle x_1>\sqrt{R}$ you have to use that $\displaystyle f(x):=\frac{1}{2}\left(\frac{R}{x}+x\right)$ is increasing in $\displaystyle [\sqrt{R},\infty)$ and $\displaystyle f(\sqrt{R})=\sqrt{R}$.

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

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

I mean that $\displaystyle f(x):=\frac{1}{2}\left(\frac{R}{x}+x\right)$, $\displaystyle 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 $\displaystyle x_n>x_{n+1}>\sqrt{R}$ for $\displaystyle 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.