Recurrence relation $T(n) = T(n/2) + n\log(n)$ So I've been working on this recurrence equation and I'm stumped at the end. $T(n) = T(n/2) + n\log(n);\: T(1) = 1;\: n = 2^k$ and $\log $ is base $2$.  
$T(2^k) = T(2^{k-1}) + 2^k \log(2^k)$
$T(2^k) = T(2^{k-1}) + (2^k) k$
$T(2^{k-1}) = T(2^{k-2}) + 2^{k-1} \log (2^{k-1})$
$T(2) = T(1) + 2^{1}\cdot(1)$
$T(1) = 1$
$T(2^k) = 1 + \displaystyle \sum_{i=0}^{ k} (2^i) (k-i)$
I'm not sure if I did everything correct, but I'm confused about tackling the summation.  

To assure you about the summation I separated the terms of the final sums in a likely better patternizable form:
$ \qquad  \qquad \displaystyle \small \begin{array} {}
T(1)&=&1 &=&1&=&3-1\cdot2\\
T(2^1)&=&1+1 \cdot2^1 &=&3&=&3+0\cdot4 \\
T(2^2)&=&1+1 \cdot2^1+2 \cdot2^2 &=&11&=&3+1\cdot8\\
T(2^3)&=&1+1 \cdot2^1+2 \cdot2^2 +3 \cdot2^3 &=& 35&=&3+2\cdot16\\
T(2^4)&=&1+ ...+4 \cdot2^4 &=& 99&=&3+3\cdot32\\
T(2^5)&=&1+ ...+5 \cdot2^5 &=& 259&=&3+4\cdot64\\
\end{array}$         
The pattern $1x+2x^2+3x^3+4x^4+...$ (where here $x=2$) can also be represented by a generating function of the style $ a/ (1-x)^2$ and this can be adapted to match the sum-expressions above as truncation of the occuring series to make the final formula below rigorous. This is the generating function:     
$ \qquad \qquad \displaystyle G(m,x)= 1+{x \cdot (1-x^{m+1})-(m+1) \cdot x^{m+1} \cdot (1-x) \over (1-x)^2}$
From this, evaluated at $x=2$ we get the expression for $T(n$)    
$ \displaystyle \qquad \qquad T(n)=G(\log_2(n),2) \\
 \qquad \qquad \qquad = 1+2 \cdot { (1-2^m)+m \cdot 2^m  \over (-1)^2} 
  \qquad \qquad \qquad  \text{ ( where } m=\log_2(n) \text{  )}\\
 \qquad \qquad \qquad = 1+2 \cdot (1-n+\log_2(n) \cdot n)   $               
and finally        
$ \qquad  \qquad  \displaystyle { T(n) = 3 + (\log_2(n)-1)\cdot2 \cdot n }$       
(which is the result as was previously given in the answer of pjhuxford)
