CLRS Exercise 2.2-3

2.2-3 Mathematical Induction

Use mathematical induction to show that when $n$ is a power of $2$ (namely $n = 2^k$), the following recurrence:

$T(n) = n\log_2(n)$

We’re going to want to treat this problem like a regular proof of induction and use the following outline:

  • Base case
  • Assumption
  • Inductive proof

#Base case

First off, we want to establish that our base case works.


Now that we’ve worked out our base case, let’s assume that the recurrence holds true for all values of $n = 2^k$ such that

#Inductive step

Next, we’ll move onto proving that it works for $n = 2^{k+1}$ such that


Technically, we could stop here because we’ve already established

However, only one trivial step is required to put the solution back in terms of $n$

which leaves us with terms of only $2^{k+1}$ which are equivalent to $n$

$ = n\log_2(n) $

Written on June 14, 2016