What is the time complexity of the recurrence T(n) = 2T(n-1) + 4

Question

What is the time complexity of the recurrence T(n) = 2T(n-1) + 4 ?

I'm having serious problems with this. I tried:

T(n) = 2T(n-1)+4 = 2(2T(n-2)+4)+4 = 4T(n-2)+12= 4(2T(n-3)+4)+4 = 8T(n-3)+20 = 8(2T(n-4)+4)+4 = 16T(n-4)+36 =…

T(n) = 2^kT(n-k) + (4+2^(k+1))

so it looks like T(n) = 2^n + (4+2^(n+1)) but it doesn't seem right... please help :(

Answer 1

Solving the recurrence relation, I found this: