The Recurrence T(n)= 2T(n-1) (2^n)-CodePudding

Can someone please help me with this ?

Use iteration method to solve it. T(n)= 2T(n-1) (2^n) , T(0) = 1

Explanation of steps would be greatly appreciated.

I tried to solve the recursion as follows

T(n)= 2T(n-1) 2^n

T(n-1) = 2T(n-2) 2^(n-1)

T(n-2) = 2T(n-3) 2^(n-2)

T(n-3) = 2T(n-4) 2^(n-3)

...

T(0) = 1

Then:

T(n) = 2^k * T(n-k) ... Here's where I get stuck.

CodePudding user response：

Well, let's compute some values for small n:

T(0) =   1
T(1) =   4
T(2) =  12
T(3) =  32
T(4) =  80
T(5) = 192

the function seems to be exponetial; we have 2^n term that's why let's check if

T(n) = f(n) * 2^n

where f(n) some unknown function. If we divide by 2^n we have f(n) = T(n) / 2^n

T(0) / 2^0 = 1
T(1) / 2^1 = 2
T(2) / 2^2 = 3
T(3) / 2^3 = 4

Looks quite clear that f(n) = n 1 and

T(n) = (n   1) * 2^n

Now let's prove it by induction.

Base: it holds for n = 0: (0 1) * 2^0 = 1

Step: from T(n - 1) = n * 2^(n - 1) we have

 T(n) = 2 * T(n - 1)   2^n =
      = 2 * n * 2^(n - 1)   2^n =
      = n * 2^n   2^n =
      = (n   1) * 2^n

So, if T(n - 1) holds, T(n) holds as well.

Q.E.D.

Close formula for

T(n) = 2T(n-1)   (2^n) 
T(0) = 1

T(n) = (n   1) * 2^n

Cheating way: try oeis (on-line encyclopedia of integer sequences) and you'll find A001787