Results 1 to 3 of 3

Thread: Solve the recurrence relation...

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    56

    Solve the recurrence relation...

    Find all solutions of the recurrence relation $\displaystyle 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 $\displaystyle r_n = \alpha 4^n +2^{n+1}$ I just don't know how to get there.
    Last edited by chickeneaterguy; Sep 9th 2010 at 02:11 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790
    I know the answer is $\displaystyle r_n = \alpha 4^n +2^{n+1}$
    This solution does not satisfy the recurrence equation. Indeed, according to this solution, $\displaystyle r_{n-1}=4^{n-1}\alpha+2^n.$ Substituting this into the equation, we get $\displaystyle 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 $\displaystyle 4^n\alpha+2\cdot2^n$.

    To solve the equation, follow these steps.

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

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

    3. Guess the regularity and write the general formula for $\displaystyle r_n$. You may use the formula $\displaystyle 2^m+\dots+1=2^{m+1}-1$, so $\displaystyle 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 $\displaystyle r_0$ is given by this formula, and that for every $\displaystyle n$, if $\displaystyle r_n$ is given by the formula, then so is $\displaystyle r_{n+1}$.
    Last edited by emakarov; Sep 10th 2010 at 05: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
    7
    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: Nov 16th 2010, 01:56 AM
  2. Solve the recurrence relation
    Posted in the Advanced Math Topics Forum
    Replies: 2
    Last Post: May 15th 2010, 05:03 PM
  3. Recurrence Relation Q
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Sep 30th 2009, 11:57 PM
  4. How to solve this recurrence relation ?
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Apr 19th 2009, 04:31 PM
  5. recurrence relation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Apr 15th 2009, 06:20 PM

Search Tags


/mathhelpforum @mathhelpforum