How to solve the following recurrence I know others have already posted about this recurrence $T(n) = 2T(n/2) + n\lg n$ on the following these two posts: post1 and post2
However, the style in which they have solved them, is not one with which I am ery familiar. I was hoping someone could look at my work so far, and then point me in the right direction or show me what I am doing wrong. This is my work up to this point:
$$T(n) = 2T(n/2) + n\lg n$$
$$=2[2T(n/2^2) + (n/2)\lg (n/2)] + n\lg n$$
$$=2^2T(n/2^2) + n\lg(n/2)+n\lg n$$
I expanded this recurrence out a bit further and finally found the general formula:
$$2^kT(n/2^k)+n\sum_{i=0}^klg(n)-lg(2^i)$$
I understand what to set $k$ equal to in order to arrive at $T(1)$, but I honestly don't understand how to simplify the summation in this problem. Should I keep the logarithm (which is base 2 by the way) in the following format $\lg(n/2^i)$ and split the summation, or is there another way to simplify this summation? I am stuck. 
EDIT
So, I made some errors in my formular when I orignally posted this. Looking at the general formula above involving $k$ now, I am still wondering how to simplify and solve it. I am not sure what to do with the $\sum_{i=0}^klg(n)$. For the $lg(2^i)$ term I am thinking I can just pull the $i$ down and pull the $lg(2) outside of the summation. 
 A: I agree (now) with your first three iterates, including the cancellation of the extra 2's I initially missed in my comments. I'd like for simplicity to state the general pattern I noticed in terms of beginning with $2^{k+1}T(1/2^{k+1}).$ I get
$$T(n)=2^{k+1}T(1/2^{k+1})+n\  [ \lg (n)+\lg (n/2)+\lg(n/4)+ \cdots + \lg(n/2^{k}).] \tag{1}$$
The log terms inside the square brackets may be combined into a single log by using the sum of logs equal to the log of the product. For the product we have a numerator of $n^k$ since there are $k$ terms each with numerator $n$. The product of denominators is
$2^0 \cdot 2^1 \cdots 2^k=2^{0+1+\cdots+k}=2^{k(k+1)/2}.$ So the sum of logs  inside square brackets in $(1)$ is the single log
$$\lg \frac{n^k}{2^{k(k+1)/2}}.$$
Of course since it is log base 2 one may go one more step to $k \lg n -[k(k+1)/2]$ but I don't see much advantage in that.
A: There  is another  closely  related recurrence  that  admits an  exact
solution.  Suppose we  have  $T(0)=0$ and $T(1)=1$ and for  $n\ge  2$
$$T(n) = 2 T(\lfloor n/2 \rfloor) + n \lfloor\log_2 n\rfloor.$$
Furthermore let the base two representation of $n$ be
$$n = \sum_{k=0}^{\lfloor \log_3 n \rfloor} d_k 2^k.$$
Then we  can unroll the  recurrence to obtain the  following exact
formula for $n\ge 1$
$$T(n) = 2^{\lfloor \log_2 n \rfloor} +
 \sum_{j=0}^{\lfloor \log_2 n \rfloor} 
2^j (\lfloor \log_2 n \rfloor - j) \left(
\sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j}
\right).$$
Now to get an upper bound consider a string of one digits which yields
$$T(n) \le 2^{\lfloor \log_2 n \rfloor} +
 \sum_{j=0}^{\lfloor \log_2 n \rfloor} 
(\lfloor \log_2 n \rfloor - j) \left(
\sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^k
\right).$$ 
Note that this bound is attained and cannot be improved. It simplifies
to
$$\lfloor \log_2 n \rfloor^2 2^{\lfloor \log_2 n \rfloor}
+ \lfloor \log_2 n \rfloor 2^{\lfloor \log_2 n \rfloor}
- 2^{\lfloor \log_2 n \rfloor} + \lfloor \log_2 n \rfloor + 2.$$
The lower bound is for the case of a one digit followed by a string of
zeros and yields
$$T(n) \ge 2^{\lfloor \log_2 n \rfloor} +
2^{\lfloor \log_2 n \rfloor} \times
\sum_{j=0}^{\lfloor \log_2 n \rfloor} 
(\lfloor \log_2 n \rfloor - j),$$
which simplifies to
$$\frac{1}{2} \lfloor \log_2 n \rfloor^2 2^{\lfloor \log_2 n \rfloor}
+ \frac{1}{2} \lfloor \log_2 n \rfloor 2^{\lfloor \log_2 n \rfloor}
+ 2^{\lfloor \log_2 n \rfloor}.$$

Joining the dominant terms of the upper and the lower bound we obtain
the asymptotics
$$\lfloor \log_2 n \rfloor^2 2^{\lfloor \log_2 n \rfloor}
\in \Theta\left(\log^2 n \times 2^{\log_2 n}\right) 
= \Theta\left(n \log^2 n\right).$$
This MSE link points to additional calculations of this type.
