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.

#Assumption

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

Proof:

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