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.

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

Hello, ob1!

I was taught an entirely different method.

The first few terms are: .

Subtract [2] - [1]: .

Subtract [4] - [3]: .

And we have: .

Let

Divide by

Factor: .

Let