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.  
 A: Your working is mostly fine, except the final summation.
So for any $i\geq1$, as you showed:
\begin{align*}
T(2^i)&=T(2^{i-1})+i\cdot2^i \\
\implies T(2^i)-T(2^{i-1})&=i\cdot2^i \\
\implies \sum_{i=1}^k (T(2^i)-T(2^{i-1})) &= \sum_{i=1}^k i\cdot2^i
\end{align*}
The left side telescopes, giving $T(2^k)-T(1)=T(2^k)-1$, so we have
$$T(2^k)=1+\sum_{i=1}^k i\cdot2^i$$
Now, to evaluate this summation, I'm not too sure of a direct way of the top of my head. If you happen to know it in advance, its not too bad to prove by induction.
I claim that $$\sum_{i=1}^k i\cdot2^i=(k-1)2^{k+1}+2$$
You can check it holds when $k=1$. Suppose it holds when $k=n$. Then:
\begin{align*}
\sum_{i=1}^{n+1}i\cdot2^i&=(n+1)2^{n+1}+\sum_{i=1}^n i\cdot2^i \\
&=(n+1)2^{n+1}+(n-1)2^{n+1}+2 \\
&= n2^{n+2}+2 \\
&= ((n+1)-1)2^{(n+1)+1}+2
\end{align*}
So the formula also holds when $k=n+1$. This proves the clame, and consequently
$$T(2^k)=1+(k-1)2^{k+1}+2=(k-1)2^{k+1}+3$$
If you wanted to rewrite this in terms of $n$, just use the fact that $2^k=n$ and $\log n=k$ (using $\log$ to base 2). Then, provided $n$ is a power of 2, the recurrence becomes:
$$T(n)=2n(\log(n)-1)+3$$
A: 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)
