Results 1 to 13 of 13

Thread: Prove monotonous decrease and bound of recursive sequence.

  1. #1
    Newbie
    Joined
    Sep 2009
    Posts
    4

    Prove monotonous decrease and bound of recursive sequence.

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

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

    Is that a rigorous proof?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member redsoxfan325's Avatar
    Joined
    Feb 2009
    From
    Swampscott, MA
    Posts
    943
    Ignore post. See discussion of problem below.
    Last edited by redsoxfan325; Sep 22nd 2009 at 01:42 PM. Reason: I was incorrect.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2009
    Posts
    4
    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 \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:
    \begin{array}{rcl}<br />
\alpha & > & 0\\<br />
x_{n} & > & \sqrt{\alpha}>0\\<br />
x_{n} & > & 0\\<br />
x_{n+1} & > & 0\\<br />
\frac{1}{2}(x_{n}+\frac{\alpha}{x_{n}}) & > & 0\\<br />
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..
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member bkarpuz's Avatar
    Joined
    Sep 2008
    From
    R
    Posts
    481
    Thanks
    2
    Quote Originally Posted by redsoxfan325 View Post
    Looks good to me. What you're doing isn't really induction. It's just manipulating the equations.

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

    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...
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member redsoxfan325's Avatar
    Joined
    Feb 2009
    From
    Swampscott, MA
    Posts
    943
    When I took the limit we already knew that it was monotonically decreasing and bounded below by 0.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member bkarpuz's Avatar
    Joined
    Sep 2008
    From
    R
    Posts
    481
    Thanks
    2

    Cool

    Quote Originally Posted by redsoxfan325 View Post
    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 x(n)>\sqrt{\alpha} yet, we only know this for 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
    f(\lambda):=\frac{1}{2}\bigg(\lambda+\frac{\alpha}  {\lambda}\bigg)....for \lambda\in(0,\infty).
    So the rational difference equation can be written as
    x(n+1)=f(x(n))....for n\in\mathbb{N}.....(1)
    Then, we see that
    f^{\prime}(\sqrt{\alpha})=0, f(0)=f(\infty)=\infty and f(\sqrt{\alpha})=\sqrt{\alpha},....(2)
    i.e., f attains its minimum value at \sqrt{\alpha} with the minimum value \sqrt{\alpha} which is at the same time the unique equilibrium of the rational difference equation, i.e., there is no value \lambda\in(0,\infty)\backslash\{\sqrt{\alpha}\} such that f(\lambda)=\lambda.
    Now, define g(\lambda):=\lambda-f(\lambda)....for \lambda\in(0,\infty).
    Here is the most important part.
    Clearly, g^{\prime}(\lambda)=(\lambda^{2}+\alpha)/(2\lambda^{2})>0....for all \lambda\in(0,\infty).
    And g(\sqrt{\alpha})=\sqrt{\alpha}-f\big(\sqrt{\alpha}\big)=0, which yields g(\lambda)>0....for all \lambda\in(\sqrt{\alpha},\infty), i.e.,
    \lambda>f(\lambda)>f(\sqrt{\alpha})=\sqrt{\alpha}....for all \lambda\in(\sqrt{\alpha},\infty).....(3)

    See the following graphic.

    Red: \nu=\lambda, Blue: \nu=f(\lambda), and Green: \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 x(1)>\sqrt{\alpha}, then taking f on both sides by considering (3), we have
    x(1)>f\big(x(1)\big)=x(2)>\alpha.....(4)
    Then similarly considering (3) and (4), we have
    x(2)>f\big(x(2)\big)=x(3)>\alpha, and by the emerging pattern, we have in general that
    x(1)>x(n)>x(n+1)>\alpha....for all n\in\mathbb{N},
    which implies that the sequence is decreasing and so it has a finite limit, more precisely, \ell\in[\sqrt{\alpha},x(1)), where \ell:=\lim\nolimits_{n\to\infty}x(n).
    The rest is simple, passing now to limit as n\to\infty on both sides of (1) and using (2), we learn that \ell=\sqrt{\alpha}.
    This completes the solution.
    Last edited by bkarpuz; Sep 22nd 2009 at 07:34 AM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member redsoxfan325's Avatar
    Joined
    Feb 2009
    From
    Swampscott, MA
    Posts
    943
    Quote Originally Posted by bkarpuz View Post
    I don't think so, since we don't know that x(n)>\sqrt{\alpha} yet, we only know this for n=1, it should be repeated by induction.
    We don't need to know that x_n>\sqrt(\alpha). All we need to know to take the limit of a sequence x_n as n\to\infty is that x_n converges. But we know x_n converges because it is monotonic and bounded. (This is a theorem.)
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member bkarpuz's Avatar
    Joined
    Sep 2008
    From
    R
    Posts
    481
    Thanks
    2

    Exclamation

    Quote Originally Posted by redsoxfan325 View Post
    We don't need to know that x_n>\sqrt(\alpha). All we need to know to take the limit of a sequence x_n as n\to\infty is that x_n converges. But we know 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 \{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 x(n)>\sqrt{\alpha} for all n\in\mathbb{N} but we only know it for n=1.
    Please don't get me wrong, I just want to clarify the situation.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member redsoxfan325's Avatar
    Joined
    Feb 2009
    From
    Swampscott, MA
    Posts
    943
    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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member bkarpuz's Avatar
    Joined
    Sep 2008
    From
    R
    Posts
    481
    Thanks
    2

    Exclamation

    Quote Originally Posted by redsoxfan325 View Post
    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 x(n)>\sqrt{\alpha}, we only know x(1)>\sqrt{\alpha}, so that proof is not complete.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Super Member redsoxfan325's Avatar
    Joined
    Feb 2009
    From
    Swampscott, MA
    Posts
    943
    I'm not claiming that x_n>\sqrt{\alpha}. I'm saying only that x_n>0.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Senior Member bkarpuz's Avatar
    Joined
    Sep 2008
    From
    R
    Posts
    481
    Thanks
    2

    Exclamation

    Quote Originally Posted by redsoxfan325 View Post
    I'm not claiming that x_n>\sqrt{\alpha}. I'm saying only that 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 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.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Super Member redsoxfan325's Avatar
    Joined
    Feb 2009
    From
    Swampscott, MA
    Posts
    943
    Quote Originally Posted by bkarpuz View Post
    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 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)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove the following Power Series is monotonous
    Posted in the Calculus Forum
    Replies: 6
    Last Post: Nov 24th 2011, 10:23 AM
  2. Replies: 2
    Last Post: Mar 1st 2010, 11:57 AM
  3. recursive sequence
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: Apr 29th 2009, 05:15 AM
  4. recursive sequence
    Posted in the Calculus Forum
    Replies: 3
    Last Post: Jan 14th 2009, 06:33 AM
  5. recursive sequence
    Posted in the Calculus Forum
    Replies: 1
    Last Post: Jul 5th 2008, 11:21 PM

Search Tags


/mathhelpforum @mathhelpforum