Need help about solving a recurrence relation
For $\sum_{0 \le r \le k} r \cdot 2^r$, start with:
$$
\frac{1 - z^{k + 1}}{1 - z} = \sum_{0 \le r \le k} z^r
$$
As this is a polynomial, the following mangling doesn't need any justification:
$$
z \frac{d}{dz} \frac{1 - z^{k + 1}}{1 - z} = \sum_{0 \le r \le k} r z^r
$$
Doing the operations indicated:
$$
\sum_{0 \le r \le k} r z^r = \frac{z^k (k z^2 - (k + 1) z) + z}{(1 - z)^2}
$$
Finally:
$$
\sum_{0 \le r \le k} r 2^r = (2 k - 2) 2^k + 2 = \Theta(k 2^k) = \Theta(n \log n)
$$