Need help about solving a recurrence relation I have a recurrence relation which is like the following:
$$
T(n) = 2T(n/2) + \log_2 n.
$$
I am using recursion tree method to solve this. And at the end, i came up with the following equation:
$$
T(n)=(2\log_2 n)(n-1)-(1*2 + 2*2^2 + \ldots + k*2^k)
$$ 
where $k=\log_2 n$.
I am trying to find a theta notation for this equation. But i cannot find a closed formula for the sum 
$$
1*2 + 2*2^2 + \ldots + k*2^k.$$ 
How can i find a big theta notation for $T(n)$? 
Thanks.
 A: $$T(n) = 2 T(n/2) + \log_2(n)$$
Let $n=2^m$ and $T(2^m) = g(m)$. Then the recurrence can be rewritten as
\begin{align}
g(m) & = 2g(m-1) + m\\
& = 2(2g(m-2) + m-1) + m\\
& = 4g(m-2) + 2(m-1) + m\\
& = 4(2g(m-3) + m-2) + 2(m-1) + m\\
& = 8g(m-3) + 4(m-2) + 2(m-1) + m\\
& = 16 g(m-4) + 8(m-3) + 4(m-2) + 2(m-1) + m
\end{align}
Hence, by induction, we have
\begin{align}
g(m) & = 2^m g(0) + \sum_{k=1}^m 2^{m-k}k = 2^m g(0) + 2^m \sum_{k=1}^m \dfrac{k}{2^k}\\
& = 2^m g(0) + 2^m \left(2 - \dfrac{m+2}{2^m}\right) = 2^m(2+g(0)) - (m+2)
\end{align}
where
$$\sum_{k=1}^m kx^k = x \dfrac{d}{dx}\left(\sum_{k=0}^m x^k\right) = x \dfrac{dx}{dx} \left(\dfrac{1-x^{m+1}}{1-x}\right) = x \cdot \left(\dfrac{mx^{m+1} - (m+1)x^m+1}{(1-x)^2} \right)$$
Hence,
$$T(n) = (2+T(1))n - (2+\log_2(n))$$
A: As observed by Marvis, the sequence $x_m=T(2^m)$ satisfies the first order linear recurrence formula
$$
x_m=2x_{m-1}+m.
$$
The homogeneous equation $x_m=2x_{m-1}$ has general solution $x_m=C2^m$. This can be checked by induction, but it follows easily from the general theory of homogeneous linear recurrence sequences.
Since the non homogeneous part is a degree $1$ polynomial, we look for a particular solution of the form $x_m=Am+B$. This is called the method of undetermined coefficients. Plugging this is the formula yields
$$
Am+B=2(A(m-1)+B)+m.
$$
So we get a solution if we take $A=-1$ and $B=-2$. Namely $x_m=-m-2$.
Finally, the general solution is the sum of the general homogeneous solution and the particular solution, namely $x_m=C2^m-m-2$. Making $m=0$ yields $x_0=C-2$ so
$$
x_m=(x_0+2)2^m-m-2.
$$
Going back to $T(n)$, this can be expressed as
$$
T(n)=(T(1)+2)n-\log_2n -2
$$
for all powers of $2$.
A: Let $T(0)=0$ and let the recurrence relation be
$$ T(n) = 2 T(n/2) + \lfloor \log_2 n \rfloor.$$
Furthermore let the binary representation of $n$ be
$$ n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k.$$
Then it is not difficult to see that
$$ T(n) = \sum_{j=0}^{\lfloor \log_2 n \rfloor} 2^j (\lfloor \log_2 n \rfloor-j) =
\lfloor \log_2 n \rfloor \sum_{j=0}^{\lfloor \log_2 n \rfloor} 2^j
- \sum_{j=0}^{\lfloor \log_2 n \rfloor} 2^j j =
2^{\lfloor \log_2 n \rfloor+1} -\lfloor \log_2 n \rfloor - 2.$$
This formula holds for all $n$ and not just powers of two.
This recurrence is so simple it does not depend on the actual values of the bits that form $n$, but only on their number. Simplifying, we obtain
$$ T(n) = 2^{\lfloor \log_2 n \rfloor+1}-\lfloor \log_2 n \rfloor - 2 \in \Theta(n).$$
This procedure is employed in a somewhat more sophisticated manner at the following link.
