# Thread: Prove monotonous decrease and bound of recursive sequence.

1. ## Prove monotonous decrease and bound of recursive sequence.

Given $\displaystyle \alpha > 0$ , $\displaystyle x_1 >\sqrt{\alpha}$, and $\displaystyle x_{n+1} = \frac{1}{2}(x_n + \frac{\alpha}{x_n})$
I need to show monotonous decrease, and $\displaystyle \lim_{n\to\infty} x_n = \sqrt{\alpha}$

I can show monotonous decrease like this:
$\displaystyle \begin{array}{rcl} x_{n} & > & \sqrt{\alpha}\\ x_{n}^{2} & > & \alpha\\ x_{n} & > & \frac{\alpha}{x_{n}}\\ 2x_{n} & > & x_{n}+\frac{\alpha}{x_{n}}\\ x_{n} & > & \frac{1}{2} (x_{n} + \frac{\alpha}{x_{n}})\\ x_{n} & > & x_{n+1}\end{array}$
but I'm not sure if that's proper induction, because the assumption step ($\displaystyle x_{n} > \sqrt{\alpha}$) doesn't match the final step.

Is that a rigorous proof?

2. Ignore post. See discussion of problem below.

3. Right, that's what I thought. I'm wondering if it can be done by induction at all, because of the x_n and the 1/x_n which don't seem to cancel if you're doing it for x_n+2. Anyway, maybe that will do.

The reason I wanted to prove monotony was that it's not safe to assume$\displaystyle \lim_{n\to\infty} x_{n+1} = \lim_{n\to\infty} x_{n}$ until you can prove they're converging. I showed that x is always positive (bounded below by zero) by a similar method:
$\displaystyle \begin{array}{rcl} \alpha & > & 0\\ x_{n} & > & \sqrt{\alpha}>0\\ x_{n} & > & 0\\ x_{n+1} & > & 0\\ \frac{1}{2}(x_{n}+\frac{\alpha}{x_{n}}) & > & 0\\ x_{n}^{2}+\alpha & > & 0\end{array}$
which is true since since both x_n and alpha are positive. Not sure if that's safe to say..

4. Originally Posted by redsoxfan325
Looks good to me. What you're doing isn't really induction. It's just manipulating the equations.

For the limit, taking $\displaystyle n\to\infty$ gives you

$\displaystyle x=\frac{1}{2}\left(x+\frac{\alpha}{x}\right)\impli es 2x=x+\frac{\alpha}{x}\implies 2x^2=x^2+\alpha\implies x^2=\alpha\implies x=\sqrt{\alpha}$
You can not take limit before showing that the sequence has a limit or is monotonic...

5. When I took the limit we already knew that it was monotonically decreasing and bounded below by 0.

6. Originally Posted by redsoxfan325
When I took the limit we already knew that it was monotonically decreasing and bounded below by 0.
I don't think so, since we don't know that $\displaystyle x(n)>\sqrt{\alpha}$ yet, we only know this for $\displaystyle n=1$, it should be repeated by induction.
Therefore the proof for the decreasing behaviour by naught101 is not actually a good one.
Here is what I have, I hope you will find it rigorous.

Let
$\displaystyle f(\lambda):=\frac{1}{2}\bigg(\lambda+\frac{\alpha} {\lambda}\bigg)$....for $\displaystyle \lambda\in(0,\infty)$.
So the rational difference equation can be written as
$\displaystyle x(n+1)=f(x(n))$....for $\displaystyle n\in\mathbb{N}$.....(1)
Then, we see that
$\displaystyle f^{\prime}(\sqrt{\alpha})=0$, $\displaystyle f(0)=f(\infty)=\infty$ and $\displaystyle f(\sqrt{\alpha})=\sqrt{\alpha}$,....(2)
i.e., $\displaystyle f$ attains its minimum value at $\displaystyle \sqrt{\alpha}$ with the minimum value $\displaystyle \sqrt{\alpha}$ which is at the same time the unique equilibrium of the rational difference equation, i.e., there is no value $\displaystyle \lambda\in(0,\infty)\backslash\{\sqrt{\alpha}\}$ such that $\displaystyle f(\lambda)=\lambda$.
Now, define $\displaystyle g(\lambda):=\lambda-f(\lambda)$....for $\displaystyle \lambda\in(0,\infty)$.
Here is the most important part.
Clearly, $\displaystyle g^{\prime}(\lambda)=(\lambda^{2}+\alpha)/(2\lambda^{2})>0$....for all $\displaystyle \lambda\in(0,\infty)$.
And $\displaystyle g(\sqrt{\alpha})=\sqrt{\alpha}-f\big(\sqrt{\alpha}\big)=0$, which yields $\displaystyle g(\lambda)>0$....for all $\displaystyle \lambda\in(\sqrt{\alpha},\infty)$, i.e.,
$\displaystyle \lambda>f(\lambda)>f(\sqrt{\alpha})=\sqrt{\alpha}$....for all $\displaystyle \lambda\in(\sqrt{\alpha},\infty)$.....(3)

See the following graphic.

Red: $\displaystyle \nu=\lambda$, Blue: $\displaystyle \nu=f(\lambda)$, and Green: $\displaystyle \nu=\sqrt{\alpha}$.

Codes of the graphic for Mathematica 7.0
Code:
Show[{Plot[{\[Lambda],1/2(\[Lambda]+1/\[Lambda]),1},{\[Lambda],0,3},PlotRange->{{0,3},{0,3}},PlotStyle->{{Red},{Blue},{Green}},AxesOrigin->{0,0},AxesLabel->{\[Lambda],\[Nu]},LabelStyle->Directive[White,Large]],Graphics[{Text[Style[Sqrt[\[Alpha]]],{2.7,0.8}],Text[Style["f"],{2.7,1.4}],Text[Style["I"],{2.7,2.5}]}]}]
Now, we are ready to finalize the proof.
Let $\displaystyle x(1)>\sqrt{\alpha}$, then taking $\displaystyle f$ on both sides by considering (3), we have
$\displaystyle x(1)>f\big(x(1)\big)=x(2)>\alpha$.....(4)
Then similarly considering (3) and (4), we have
$\displaystyle x(2)>f\big(x(2)\big)=x(3)>\alpha$, and by the emerging pattern, we have in general that
$\displaystyle x(1)>x(n)>x(n+1)>\alpha$....for all $\displaystyle n\in\mathbb{N}$,
which implies that the sequence is decreasing and so it has a finite limit, more precisely, $\displaystyle \ell\in[\sqrt{\alpha},x(1))$, where $\displaystyle \ell:=\lim\nolimits_{n\to\infty}x(n)$.
The rest is simple, passing now to limit as $\displaystyle n\to\infty$ on both sides of (1) and using (2), we learn that $\displaystyle \ell=\sqrt{\alpha}$.
This completes the solution.

7. Originally Posted by bkarpuz
I don't think so, since we don't know that $\displaystyle x(n)>\sqrt{\alpha}$ yet, we only know this for $\displaystyle n=1$, it should be repeated by induction.
We don't need to know that $\displaystyle x_n>\sqrt(\alpha)$. All we need to know to take the limit of a sequence $\displaystyle x_n$ as $\displaystyle n\to\infty$ is that $\displaystyle x_n$ converges. But we know $\displaystyle x_n$ converges because it is monotonic and bounded. (This is a theorem.)

8. Originally Posted by redsoxfan325
We don't need to know that $\displaystyle x_n>\sqrt(\alpha)$. All we need to know to take the limit of a sequence $\displaystyle x_n$ as $\displaystyle n\to\infty$ is that $\displaystyle x_n$ converges. But we know $\displaystyle x_n$ converges because it is monotonic and bounded. (This is a theorem.)
@redsoxfan325: Can you please tell me in which post we have shown boundedness or decreasing nature of $\displaystyle \{x(n)\}_{n\in\mathbb{N}}$?
I would like to have your attention that it is not shown in the first post since we don't know $\displaystyle x(n)>\sqrt{\alpha}$ for all $\displaystyle n\in\mathbb{N}$ but we only know it for $\displaystyle n=1$.
Please don't get me wrong, I just want to clarify the situation.

9. naught101 showed that it was monotonically decreasing in the first post. And it is bounded below by zero simply because the first term is positive, and the sequence is defined recursively using only division and addition of positive numbers, so there is no possibility of any of the terms being less then zero.

10. Originally Posted by redsoxfan325
naught101 showed that it was monotonically decreasing in the first post. And it is bounded below by zero simply because the first term is positive, and the sequence is defined recursively using only division and addition of positive numbers, so there is no possibility of any of the terms being less then zero.
@redsoxfan325: my dear friend would you please read my previous post and the first carefully.
We do not know $\displaystyle x(n)>\sqrt{\alpha}$, we only know $\displaystyle x(1)>\sqrt{\alpha}$, so that proof is not complete.

11. I'm not claiming that $\displaystyle x_n>\sqrt{\alpha}$. I'm saying only that $\displaystyle x_n>0$.

12. Originally Posted by redsoxfan325
I'm not claiming that $\displaystyle x_n>\sqrt{\alpha}$. I'm saying only that $\displaystyle x_n>0$.
Do you mean boundedness from below imply convergence of a sequence?
If so, every nonnegative sequence would be convergent, but not.

Please refer to the first post again, while naught101 was trying to prove decreasing behaviour of the solution he/she assumed $\displaystyle x(n)>\sqrt{\alpha}$ (which is not proved), so that we still don't know that the sequence is decreasing (which implies boundedness from above).
Therefore, we don't know whether the limit of the solution exists or not, and therefore, we can not pass to limit on both sides of the equation.
That's all I want to mention.
I think you have missed some parts of the discussion.

13. Originally Posted by bkarpuz
Do you mean boundedness from below imply convergence of a sequence?
If so, every nonnegative sequence would be convergent, but not.

Please refer to the first post again, while naught101 was trying to prove decreasing behaviour of the solution he/she assumed $\displaystyle x(n)>\sqrt{\alpha}$ (which is not proved), so that we still don't know that the sequence is decreasing (which implies boundedness from above).
Therefore, we don't know whether the limit of the solution exists or not, and therefore, we can not pass to limit on both sides of the equation.
That's all I want to mention.
I think you have missed some parts of the discussion.
I read naught101's proof incorrectly. I thought he had proved the monotonically decreasing part but he sort of "spliced" two separate proofs and I didn't even notice. So you're right. We didn't yet know that it was monotonically decreasing.

The theorem I was referring to states that (in a complete metric space):

"If a sequence is monotonically decreasing and bounded below, then it converges." (and vice-versa)