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

1. ## 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.

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

Hello, ob1!

I was taught an entirely different method.

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

$\displaystyle \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]: .$\displaystyle T(n+1)-T(n) \:=\:2\!\cdot\!T(n) - 2\!\cdot\!T(n-1) + 2$

$\displaystyle \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]: .$\displaystyle 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: .$\displaystyle T(n+2) - 4\!\cdot\!T(n+1) + 5\!\cdot\!T(n) + 2\!\cdot\!T(n-1) \;=\;0$

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

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

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

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

$\displaystyle \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}$

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

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

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

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

$\displaystyle \text{Therefore: }\;f(n) \;=\;-4 - 2n + \tfrac{7}{2}\!\cdot\!2^n$