Results 1 to 5 of 5

Math Help - Limits of recursive sequences

  1. #1
    Junior Member
    Joined
    Nov 2009
    Posts
    29

    Limits of recursive sequences

    I am trying to figure out how can i get limit of recursive sequence.
    For example this one.
    a_1=1
    a_{n+1}=\frac{a_n}{2}+1

    Is there any common way of solving all recursive limits?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,373
    Thanks
    1315
    Quote Originally Posted by PJani View Post
    I am trying to figure out how can i get limit of recursive sequence.
    For example this one.
    a_1=1
    a_{n+1}=\frac{a_n}{2}+1

    Is there any common way of solving all recursive limits?
    IF the limit exists, then take the limit of both sides of the recursion equation: \lim a_{n+1}= \frac{\lim a_n}{2}+ 1. If the limit exists and \lim a_n= a, then both of those limits are a. You get the equation a= \frac{a}{2}+ 1. Solve that equation for a.

    Of course, that only works if the sequence converges. Here you can see that the first few numbers are 1, 3/2, 7/4, .... You should be able to prove, by induction, that this sequence is increasing and has 2 as an upper bound. By the "monotone sequence theorem", then, the sequence converges.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    The sequence is defined by the recursive equation...

    a_{n}= 1+ \frac{a_{n-1}}{2} (1)

    ... and from (1) we derive that...

    \Delta_{n} = a_{n}-a_{n-1}= 2 - a_{n} (2)

    The sequence admits finite limit if and only if \lim_{n \rightarrow \infty} \Delta_{n}=0 , so that from (2) we derive...

    \lim_{n \rightarrow \infty} a_{n}=2 (3)

    Kind regards

    \chi \sigma
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Nov 2009
    Posts
    29
    HallsofIvy and chisigma:
    thank you two

    I know how to make induction on explicit sequences but i don't know how to make induction on recursive equations.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,373
    Thanks
    1315
    Recursive sequences, because they give an explicit formula for x_{n+1} in terms of x_n, are easier to use with induction!

    For example, to prove this sequence is increasing:
    1) If n= 1, a_n= a_1= 1 and a_{n+1}= a_2= \frac{a_1}{2}+ 1= \frac{1}{2}+ 1= \frac{3}{2} so a_2> a_1.

    2) Assume that, for some k, a_{k+1}> a_k. Then a_{k+2}= \frac{a_{k+1}}{2}+ 1> \frac{a_k}{2}+ 1= x_{k+1}.
    (I have used the fact that, since a_{k+1}> a_k, \frac{a_{k+1}}{2}> \frac{a_k}{2}.)

    Its just as easy to prove that 2 is an upper bound for the sequence.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Solving recursive sequences
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 21st 2010, 02:38 PM
  2. sequences by primitive recursive rules?
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: January 31st 2010, 03:45 AM
  3. Recursive Formulas & Sequences
    Posted in the Calculus Forum
    Replies: 3
    Last Post: April 30th 2009, 11:17 PM
  4. Sequences and the Recursive rule
    Posted in the Algebra Forum
    Replies: 3
    Last Post: March 6th 2008, 11:35 PM
  5. recursive sequences!
    Posted in the Calculus Forum
    Replies: 13
    Last Post: January 24th 2008, 05:39 PM

Search Tags


/mathhelpforum @mathhelpforum