Results 1 to 2 of 2

Math Help - Recurrence Relations with 2n? Where am I going wrong?

  1. #1
    ob1
    ob1 is offline
    Newbie
    Joined
    Mar 2013
    From
    America
    Posts
    2

    Recurrence Relations with 2n? Where am I going wrong?

    hello guys,

    I have been working on this problem for hours... And I am banging my head against the wall.. Please tell me where I went wrong, and whats the right answer.

    T(n) = 2T(n-1) + 2n, T(1)=1

    Here is what I got

    2^4T(n-4)+2^4(N-3)+2^3(n-2)+2^2(n-1)+2n

    I ended up doing the 2S strategy and subtracting 2s from s

    2S= 2^nT(1)+2^n-2(2)+2^n-2(3)...2^2n

    2S-S = 2^n+2^n-1+2^n-2...+2^2n-2n

    Now I have no Idea what to do. Any help would be awesome.

    Thank you guys.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,547
    Thanks
    539

    Re: Recurrence Relations with 2n? Where am I going wrong?

    Hello, ob1!

    I was taught an entirely different method.


    T(n) \,=\, 2\!\cdot\!T(n-1) + 2n,\quad T(1)=1
    The first few terms are: . T(1) = 1,\;\;T(2) = 6,\;\;T(3) = 18\;\hdots

    \begin{array}{ccccccc}\text{We are given:} & T(n) &=& 2\!\cdot\!T(n-1) + 2n & [1] \\ \text{Next term:} & T(n+1) &=& 2\!\cdot\!T(n) + 2(n+1) & [2]\end{array}

    Subtract [2] - [1]: . T(n+1)-T(n) \:=\:2\!\cdot\!T(n) - 2\!\cdot\!T(n-1) + 2

    \begin{array}{ccccccc}\text{So we have:} & T(n+1) &=& 3\!\cdot\!T(n) - 2\!\cdot\!T(n-1) + 2 & [3] \\ \text{Next term:} & T(n+2) &=& 3\!\cdot\!T(n+1) - 2\!\cdot\!T(n) + 2 & [4] \end{array}

    Subtract [4] - [3]: . T(n+2) - T(n+1) \:=\:3\!\cdot\!T(n+1) - 3\!\cdot\!T(n) - 2\!\cdot\!T(n) + 2\!\cdot\!T(n-1)

    And we have: . T(n+2) - 4\!\cdot\!T(n+1) + 5\!\cdot\!T(n) + 2\!\cdot\!T(n-1) \;=\;0

    Let X^n \,=\,T(n)\!:\;\;X^{n+2} - 4X^{n+1} + 5X^n + 2X^{n-1}\;=\;0

    Divide by X^{n-1}\!:\;\;X^3 - 4X^2 + 5X - 2

    Factor: . (X-1)(X-1)(X-2) \;=\;0 \quad\Rightarrow\quad X \:=\:1,1,2


    Let f(n) \;=\;A + B\!\cdot\!n + C\!\cdot\!2^n

    \begin{array}{ccccccc}f(1) = 1: & A + B + 2C &=& 1 & (1) \\ f(2) = 6: & A + 2B + 4C &=& 6 & (2) \\ f(3) = 18: & A + 3B+8C &=& 18 & (3) \end{array}

    \begin{array}{ccccccc}\text{Subtract (2) - (1):} & B+2C &=& 5 & (4) \\ \text{Subtract (3) - (2):} & B+4C &=&12 & (5) \end{array}

    \text{Subtract (5) - (4):}\;\;2C = 7 \quad\Rightarrow\quad \boxed{C = \tfrac{7}{2}}

    \text{Substitute into (4):}\;\;B + 2\left(\tfrac{7}{2}\right) \,=\,5 \quad\Rightarrow\quad\boxed{B = \text{-}2}

    \text{Substitute into (1)L} \;\;A - 2 + 2(\tfrac{7}{2}) \:=\:1 \quad\Rightarrow\quad \boxed{A = \text{-}4}


    \text{Therefore: }\;f(n) \;=\;-4 - 2n + \tfrac{7}{2}\!\cdot\!2^n
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence Relations
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: June 7th 2009, 04:14 PM
  2. recurrence relations - degree of the recurrence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 6th 2009, 07:56 PM
  3. recurrence relations
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 9th 2008, 11:06 AM
  4. recurrence relations help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 19th 2008, 09:08 PM
  5. help with recurrence relations
    Posted in the Algebra Forum
    Replies: 1
    Last Post: August 11th 2008, 05:07 PM

Search Tags


/mathhelpforum @mathhelpforum