Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've been having trouble with an assignment I received with the course I am following. The assignment in question:

Use induction to prove that when $n \geq 2$ is an exact power of $2$, the solution of the recurrence

$$T(n) = \begin{cases} 2 & \text{ if } n = 2,\\ 2T(n/2)+n & \text{ if } n =2^k, k > 1 \\ \end{cases} $$

is $T(n) = n\log(n)$

NOTE: the logarithms in the assignment have base $2$.

The base case here is obvious, when $n = 2$, we have that $2 = 2\log(2)$. However, I am stuck on the step here and I am not sure how to solve this.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

Let $T(n)=n\log{n}$, here $n=2^k$ for some k. Then I guess we have to show that equality holds for $k+1$, that is $2n=2^{k+1}$. $T(2n)=2T(n)+2n=2n\log{n}+2n=2n(\log{n}+1)=2n\log{2n}$

share|improve this answer
    
Thank you, that makes complete sense. Did not think about taking 2n, I was instead messing around with the $2^{k+1}$. Just a slight note: My question was tagged with homework, which would mean that you are not supposed to give the answer but instead give hints/tips. –  Ruddie Feb 12 '12 at 11:45
    
Oops, my bad, not used to check these tags yet –  Julius Feb 12 '12 at 11:50
    
No problem, the answer did help. And once I saw you took 2n instead of $2^{k+1}$ I figured it out myself. –  Ruddie Feb 12 '12 at 11:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.