Solution

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

= 2{2(T(n-2) + a} + a

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

... = (2^k)T(n-k) + a (2^k - 1)

When n-k = 0, we get

T(n) = (2^k) + a (2^k - 1)

Proof

T(0) = 2^0 + a (2^0 - 1) = 1 (formula true for n=1)

Assume true fro 1...k

T(k+1) = 2T(k) + a

= 2{2^k + a (2^k -1) + a}

= 2^(k+1) + 2a(2^k -1) + a

= 2^(k+1) + a(2^(k+1) -1)

therefore the formula is true for (k+1) and so for all n

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

= 2{2(T(n-2) + a} + a

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

... = (2^k)T(n-k) + a (2^k - 1)

When n-k = 0, we get

T(n) = (2^k) + a (2^k - 1)

Proof

T(0) = 2^0 + a (2^0 - 1) = 1 (formula true for n=1)

Assume true fro 1...k

T(k+1) = 2T(k) + a

= 2{2^k + a (2^k -1) + a}

= 2^(k+1) + 2a(2^k -1) + a

= 2^(k+1) + a(2^(k+1) -1)

therefore the formula is true for (k+1) and so for all n

## No comments:

## Post a Comment