Results 1 to 3 of 3

Math Help - Solve the recurrence relation...

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    56

    Solve the recurrence relation...

    Find all solutions of the recurrence relation  r_n = 4r_{n-1} +2^n

    I know how to do the linear ones but if someone could point me in the right direction to complete this one, that would be great. Thanks!

    EDIT: I know the answer is r_n = \alpha 4^n +2^{n+1} I just don't know how to get there.
    Last edited by chickeneaterguy; September 9th 2010 at 03:11 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785
    I know the answer is r_n = \alpha 4^n +2^{n+1}
    This solution does not satisfy the recurrence equation. Indeed, according to this solution, r_{n-1}=4^{n-1}\alpha+2^n. Substituting this into the equation, we get r_n=4(4^{n-1}\alpha+2^n)+2^n=4^n\alpha+4\cdot2^n+2^n=4^n\alph  a+5\cdot2^n, while it should be 4^n\alpha+2\cdot2^n.

    To solve the equation, follow these steps.

    1. Note that when r_0 is fixed, the sequence r_n is uniquely determined. Therefore, everything further will use some fixed parameter r_0.

    2. Write r_1, r_2, r_3, and r_4 explicitly (using r_0). Hint: don't compute and don't add the powers of 2; for example, leave 2^3 + 2^2 instead of 12 or 2^2(2+1).

    3. Guess the regularity and write the general formula for r_n. You may use the formula 2^m+\dots+1=2^{m+1}-1, so 2^m+2^{m-1}+\dots+ 2^{k+1}=(2^m+\dots+1)-(2^k+\dots+1)=(2^{m+1}-1)-(2^{k+1}-1)=2^{m+1}-2^{k+1}.

    4. Prove by induction that this is indeed the solution. Namely, verify that r_0 is given by this formula, and that for every n, if r_n is given by the formula, then so is r_{n+1}.
    Last edited by emakarov; September 10th 2010 at 06:21 AM. Reason: Rewrote "follow the following".
    Follow Math Help Forum on Facebook and Google+

  3. #3
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    You could also use the Z transform to solve it. The idea there is very much along the same lines as the Laplace Transform.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 16th 2010, 02:56 AM
  2. Solve the recurrence relation
    Posted in the Advanced Math Topics Forum
    Replies: 2
    Last Post: May 15th 2010, 06:03 PM
  3. Recurrence Relation Q
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 1st 2009, 12:57 AM
  4. How to solve this recurrence relation ?
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: April 19th 2009, 05:31 PM
  5. recurrence relation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 15th 2009, 07:20 PM

Search Tags


/mathhelpforum @mathhelpforum