How to solve this recursive equation?

Question

I've got this recursive equation:

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

I know I should use mathematical induction. For $n = 2$, prove is obvious. But for $2n$, it's more difficult: $$ T(2n) = 2T(n) + n $$

So how to solve that?

Answer 1

Satisfy yourself with the first few values that:

\begin{align} T(2^k)&=2T(2^{k-1})+2^k\\ &=4T(2^{k-2})+2^k+2^k\\ &=8T(2^{k-3})+3\cdot2^k\\ &\vdots\\ &=2^{k-1}T(2^1)+(k-1)\cdot2^k\\ &=2^k+(k-1)\cdot 2^k\\ &=k\cdot2^k \end{align}

So if we say $2^k=n$ then $T(n)=\log_2(n)\cdot n$

Answer 2

Assume that $n$ is a power of $2$ so that $n = 2^k$ for some $k \in \mathbb N$. Then by unrolling the recursion, observe that: \begin{align*} T(n) &= T(2^k) \\ &= 2 \cdot T(2^{k-1}) \\ &= 2^2 \cdot T(2^{k-2}) \\ &= 2^3 \cdot T(2^{k-3}) \\ &= \cdots \\ &= 2^{k-2} \cdot T(2^{2}) \\ &= 2^{k-1} \cdot T(2) \\ &= 2^{k-1} \cdot 2 \\ &= 2^k \\ &= n \end{align*}

Answer 3

For small values of $n$, we have $T(2),T(4),T(8),T(16),\ldots=2,8,24,64\ldots$

Can you find a connection between $n$ and $T(n)$?

Let $n=2^k$, and use induction on $k$. So $U(k)=T(2^k)$, and $U(k+1)=2U(k)+2^k$.