Prove recurrence relation via mathematical induction

$$T(n) = \begin{cases} 2 & \text{if } n = 2 \\ 2T(\frac{n}{2})+n & \text{if } n = 2^k \text{, for } k > 1 \end{cases}\\ \text{ } \\ \text{ } \\ \text{ } \\ \text{Prove } T(n) = n\lg(n) \text{ if } n = 2^k\text{, for } k > 1.$$

I am crawling through the "Introduction to Algorithms" textbook, in preparation for a future course, and this question has stumped me. I was able to understand proving algorithmic correctness using loop invariants, but I don't have a lot (any) experience in proofs. As a side-note, lg(n) is the binary logarithm of n. Also: The book did not make it explicit, but k is above 1 and an integer.

Here is what I have so far.

Base case
\begin{align} \text{Let } n = 2^k \text{ where } k &= 2 \text{ (minimal case)}\\ n &= 2^k = 4\\ 2T(\frac{n}{2}) + n &= n\lg n\\ 2T(2) + 4 &= 4\lg 4\\ 2*2 + 4 &= 4*2\\ 8 &= 8 \end{align}

Inductive hypothesis
$$T(2^{k+1}) = 2^{k+1}\lg{2^{k+1}}$$

Inductive step
$$2T(\frac{2^{k+1}}{2}) + 2^{k+1} = 2^{k+1}(k+1)$$

Beyond that, I cannot go. I would greatly appreciate any hints.

(I reiterate... this is not homework, I'm trying to solve this as a personal challenge)

Mentallic
Homework Helper
Now if $n=2^{k+1}$, then what does $2^{k+1}(k+1)$ equal to?

Last edited:
## 2^{k+1}(k+1) = k2^{k+1} + 2^{k+1} ##, via distribution

So...

$$2T(\frac{2^{k+1}}{2})+2^{k+1} = k2^{k+1} + 2^{k+1}\\ 2T(\frac{2^{k+1}}{2}) = k2^{k+1} \\$$

And also...

$$2T(\frac{2^{k+1}}{2}) = k2^{k+1} \\ 2T(2^k) = k2^{k+1} \\$$

If I divide by two...

$$T(2^k) = k2^k \\$$

This is neat, but it doesn't seem useful.

Edit: Wait... HOLY GOD

I understand now why some people do this for a living... the shock and elation at seeing the answer right before my eyes.

Now I just replace with my inductive hypothesis...

$$(2^k)\lg(2^k) = k2^k \\ (2^k)k = k2^k \\ \text{ } k2^k = k2^k \\$$

Last edited:
Mentallic
Homework Helper
That's fine, but not the usual systematic way of how we prove by induction.

Usually, you show the base case of k=1 or k=2 etc. is true. Then you assume the nth case to hold, that is you assume that what you are trying to prove is true:

$$T(n)=n\lg{n}, n=2^k$$
i.e.
$$T(2^k)=2^k\lg{2^k}=2^kk$$

This last expression here which is $T(2^k)=2^kk$ we assume to be true.

Now for the inductive hypothesis, we increment k by 1, which means we now test to see if

$$T(N)=N\lg{N}, N=2^{k+1}$$
(I'm using N here to denote that it's different to our previous n)

so we are trying to show that

$$T(2^{k+1})=2^{k+1}\lg\left({2^{k+1}}\right)$$

But we aren't assuming it's true. We're going to try to turn the left hand expression into the right hand expression using what we've been given.

By the recurrence relation,

$$T(2^{k+1})=2T\left(\frac{2^{k+1}}{2}\right)+2^{k+1} = 2T(2^k)+2^{k+1}$$

But from our assumption, $T(2^k)=2^kk$. Plugging this in gives us

$$T(2^{k+1})=2(2^kk)+2^{k+1}=2^{k+1}k+2^{k+1}=2^{k+1}(k+1)$$

What were we trying to show again? That

$$T(N)=N\lg{N}, N=2^{k+1}$$

So we want to express everything in terms of N.

$$T(2^{k+1})=T(N)$$
and since $\lg\left({2^{k+1}}\right)=k+1$ then
$$2^{k+1}(k+1)=2^{k+1}\lg\left({2^{k+1}}\right)=N\lg(N)$$

as required. Hence it's proven.

Ah, it took me a night's sleep to understand your response.. Today, while looking over my original solution (the one I posted before yours), I was bothered. It seems as if I was assuming something was true, and then trivially deriving it was true from that assumption (putting the cart before the horse).

Now I see how mathematical induction is supposed to work. You prove a base case, thereby clarifying that T(n) = n lg n, for the lowest n. Then you prove than n+1 (here, 2^(k+1) is true by rewriting it in terms of 2^k, which you've already proved in the base case.

Thank you for clarifying. I'm going to try proving a few recurrence relations like this... it seems now like a problem only of algebraic skill.

Mentallic
Homework Helper