1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How to prove a recursive formula converges.

  1. Jul 7, 2009 #1
    1. The problem statement, all variables and given/known data
    Prove that the recursive sequence, a_(n+1) = 2/ [ 1/3 + 1/ (4+ a_n ) ], converges.


    2. Relevant equations



    3. The attempt at a solution
    The recursive formula converges very quickly, no matter where you start, but why? and how do I prove that it is so?
     
  2. jcsd
  3. Jul 7, 2009 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    So this is
    [tex]a_{n+1}= \frac{2}{\frac{1}{3}+\frac{1}{4+a_n}}[/tex]
    [tex]= \frac{2}{\frac{7+ a_n}{3(4+a_n)}}= \frac{6(4+ a_n)}{7+ a_n}[/tex]

    If that converges to, say, a, taking the limit on both sides of that equation gives
    [tex]a= \frac{6(4+ a)}{7+ a}[/tex]
    so a(7+a)= 6(4+ a) or [itex]a^2+ 7a= 24+ 6a[/itex], [itex]a^2+ a- 24= 0[/itex] which means that the sequence converges to
    [tex]a= \frac{-1\pm\sqrt{1+ 96}}{2}= \frac{-1\pm\sqrt{97}}{2}[/tex]
    depending on whether a1 is greater than or equal to -4. (Assuming that I haven't made some silly arithmetic error which you had better check!)

    In order to prove that it does converge you could probably use "monotone convergenc": if an increasing sequence has an upper bound, then it converges and if a decreasing sequence has a lower bound, then it converges.

    [itex]\sqrt{97}< 10[/itex] so [itex](-1+\sqrt{97})/2< 9/2< 5[/itex]. You should be able to prove, probably by induction on n, that, if a1> -4, then {an} is an increasing sequence and has 5 as an upper bound.

    Similarly, [itex](-1-\sqrt{97})/2> -11/2> -6[/itex]. You should be able to prove that, if a1< -4, then {an} is a decreasing sequence and has -6 as a lower bound.
     
  4. Jul 7, 2009 #3
    Once it is written this way, there is a standard technique for analysis. It involves using the matrix
    [tex]A = \left[\begin{array} &6\qquad 24& 1\qquad 7\end{array}\right][/tex]
    So it becomes a problem in linear algebra.
     
  5. Jul 7, 2009 #4
    Is this proof valid?I don't think it's logical to take limit on both sides before you prove the squence is convergent.
     
  6. Jul 7, 2009 #5

    statdad

    User Avatar
    Homework Helper

    "Is this proof valid?I don't think it's logical to take limit on both sides before you prove the squence is convergent."

    This is a common "trick" - notice that Halls prefaced his comments by saying If this converges . You haven't formally proven it converges, but this approach can often give you

    1) An idea as to the value of the limit
    2) What type of initial conditions must hold in order for convergence to occur

    As was noted, you must still show that convergence occurs.
     
  7. Jul 7, 2009 #6
    I doubt the validity of this part, since the limit may not exist, how could we use it to prove the sequence is bounded?
     
  8. Jul 7, 2009 #7
    He's not using the limit to prove the boundedness of the sequence (that would be faulty logic: assuming what you're trying to prove). Rather, he's using what the limit would have to be IF the sequence converges to help him pick a good candidate for an upper/lower bound (notice that he didn't even suggest using the tentative limit as the bound, but rather something slightly larger/smaller than that...doing the hypothetical side calculation about what the limit would need to be IF (big if!) it exists merely gives you a good place to start looking for hand-holds get get your proof going)
     
  9. Jul 7, 2009 #8
    Ok, got it, I misunderstood the post, thanks for the clarification.
     
  10. Jul 7, 2009 #9
    Thank you, that worked well for proving that it converges. My next issue concerns determining a rate of convergence. I know how to treat a sequence in explicit form to determine what the rate of convergence is, but I don't know how to take a non-linear recurrence relation and make it explicit. Any thoughts?
     
  11. Jul 8, 2009 #10
    There is a general technique for this kind of recursive formula, but since your example is a little
    tedious to work out,I'll show you how this kind of question is solved using my example,say,
    [tex]a_{n + 1} = \frac{4 + a_n }{1 + a_n }[/tex]
    then find the fix point for the formula,let
    [tex]a = \frac{4 + a}{1 + a }[/tex]
    solve it you get [tex]a = \pm 2[/tex]
    take either value,say,-2
    then
    [tex]a_{n + 1} - ( - 2) = a_{n + 1} + 2 = \frac{4 + a_n }{1 + a_n } + 2 = \frac{3(2 + a_n )}{1 + a_n } = \frac{3(2 + a_n )}{2 + a_n - 1}
    [/tex]
    take reciprocals on both sides:
    [tex]
    \frac{1}{a_{n + 1} + 2} = \frac{1}{3} - \frac{1}{3}\frac{1}{(a_{n} + 2)}
    [/tex]
    then let
    [tex]b_n = \frac{1}{a_{n } + 2}[/tex]
    you'll get
    [tex]
    b_{n + 1} = \frac{1}{3} - \frac{1}{3}b_n
    [/tex]
    this is a linear recursive formula,then you know what to do with it.
     
    Last edited: Jul 8, 2009
  12. Jul 8, 2009 #11
    I'm not quite familiar with the matrix technique, but I guess what g_edgar said indeed is the same with mine but in matrix language, probably it'll become a problem of matrix diagolization
     
  13. Jul 8, 2009 #12
    Correct. Some expressions with [tex]\sqrt{97}[/tex] in them are the eigenvalues of the matrix.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: How to prove a recursive formula converges.
  1. Recursive formulae (Replies: 14)

  2. Convergence Recursive (Replies: 6)

Loading...