Prove recurrence relation via mathematical induction

AI Thread Summary
The discussion focuses on proving the recurrence relation T(n) = n lg n for n = 2^k using mathematical induction. The base case is established with n = 4, confirming that T(4) equals 8, which matches the expected result. The inductive hypothesis assumes T(2^k) = 2^k k, leading to the inductive step where T(2^(k+1)) is expressed in terms of T(2^k). The proof concludes by demonstrating that both sides of the equation match, validating the original statement. The participants express satisfaction in understanding the induction process and its application to recurrence relations.
ellipsis
Messages
158
Reaction score
24
$$

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)
 
Mathematics news on Phys.org
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:
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.
 
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.
 
Thread 'Video on imaginary numbers and some queries'
Hi, I was watching the following video. I found some points confusing. Could you please help me to understand the gaps? Thanks, in advance! Question 1: Around 4:22, the video says the following. So for those mathematicians, negative numbers didn't exist. You could subtract, that is find the difference between two positive quantities, but you couldn't have a negative answer or negative coefficients. Mathematicians were so averse to negative numbers that there was no single quadratic...
Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
Thread 'Unit Circle Double Angle Derivations'
Here I made a terrible mistake of assuming this to be an equilateral triangle and set 2sinx=1 => x=pi/6. Although this did derive the double angle formulas it also led into a terrible mess trying to find all the combinations of sides. I must have been tired and just assumed 6x=180 and 2sinx=1. By that time, I was so mindset that I nearly scolded a person for even saying 90-x. I wonder if this is a case of biased observation that seeks to dis credit me like Jesus of Nazareth since in reality...
Back
Top