Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|improve this answer

Your Answer


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.