[Introduction to Algorithms, CLRS] Exercises 2.3-3

This is a solution for Introduction to Algorithms. I write this for my study purpose.

Exercises 2.3-3

Use mathematical induction to show that when n is an exact power of 2, the solution of the recurrence

is T(n) = nlgn.

Answer:

For base case, when n = 2, T(2) = 2lg2 = 2

When we suppose  there's a n=2^k, such that k > 1, and it holds this equation, if n=2^(k+1) holds the equation too, then we can say that this equation holds in every case. So, by our assumption, T(2^k) = (2^k) lg (2^k).

T(2^(k+1) = 2T(2^(k+1)/2)+2^(k+1) = 2T(2^k)+2^(k+1) = 2(T(2^k)+2^k)=2( (2^k) lg (2^k) +2^k) = 2^(k+1) lg (2^(k+1)/2) + 2^(k+1) 

= 2^(k+1) lg (2^(k+1))

Therefore, we can say that this equation holds for every n, such that n=2^k, for k > 1.