Prove recurrence relation via mathematical induction

[ellipsis]

$$

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]

Now if [itex]n=2^{k+1}[/itex], then what does [itex]2^{k+1}(k+1)[/itex] equal to?

 

[ellipsis]

## 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 \\

$$

 

[Mentallic]

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:

[tex]T(n)=n\lg{n}, n=2^k[/tex]
i.e.
[tex]T(2^k)=2^k\lg{2^k}=2^kk[/tex]

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

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

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

so we are trying to show that

[tex]T(2^{k+1})=2^{k+1}\lg\left({2^{k+1}}\right)[/tex]

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,

[tex]T(2^{k+1})=2T\left(\frac{2^{k+1}}{2}\right)+2^{k+1} = 2T(2^k)+2^{k+1}[/tex]

But from our assumption, [itex]T(2^k)=2^kk[/itex]. Plugging this in gives us

[tex]T(2^{k+1})=2(2^kk)+2^{k+1}=2^{k+1}k+2^{k+1}=2^{k+1}(k+1)[/tex]

What were we trying to show again? That

[tex]T(N)=N\lg{N}, N=2^{k+1}[/tex]

So we want to express everything in terms of N.

[tex]T(2^{k+1})=T(N)[/tex]
and since [itex]\lg\left({2^{k+1}}\right)=k+1[/itex] then
[tex]2^{k+1}(k+1)=2^{k+1}\lg\left({2^{k+1}}\right)=N\lg(N)[/tex]

as required. Hence it's proven.

 

[ellipsis]

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]

Glad to hear that

Well, since all of the steps you made were invertible, then it doesn't matter which direction you approach it from, if you show that they lead to an equality in the end, then it must have been true from the beginning. It's always a good idea to take a look back at the simple stuff to refresh yourself with what the process is, especially when the questions become more complicated and distract you from the final goal.