Prove recurrence relation via mathematical induction

  • Thread starter ellipsis
  • Start date
  • #1
158
23
$$

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)
 

Answers and Replies

  • #2
Mentallic
Homework Helper
3,798
94
Now if [itex]n=2^{k+1}[/itex], then what does [itex]2^{k+1}(k+1)[/itex] equal to?
 
Last edited:
  • #3
158
23
## 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:
  • #4
Mentallic
Homework Helper
3,798
94
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.
 
  • #5
158
23
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.
 
  • #6
Mentallic
Homework Helper
3,798
94
Glad to hear that :smile:

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.
 

Related Threads on Prove recurrence relation via mathematical induction

Replies
3
Views
511
Replies
5
Views
1K
  • Last Post
Replies
11
Views
6K
  • Last Post
Replies
12
Views
856
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
5
Views
3K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
2
Views
1K
Top