How to solve the recurrence $T(n) = \frac{n}{2}T(\frac{n}{2}) + \log n$ I am trying to solve the recurrence below but I find myself stuck. 
$T(n) = \frac{n}{2}T(\frac{n}{2}) + \log n$
I have tried coming up with a guess by drawing a recurrence tree. What I have found is 
number of nodes at a level: $\frac{n}{2^{i}}$
running time at each node: $\log \frac{n}{2^{i}}$
total running time at each level: $\frac{n}{2^{i}}  \log \frac{n}{2^{i}}$
I try to sum this over through n > $\log n$ which is the height of the tree 
$$\begin{align}
\sum\limits_{i=0}^n \frac{n}{2^{i}}  \log \frac{n}{2^{i}}&=
n \sum\limits_{i=0}^n \frac{1}{2^{i}}  \log \frac{n}{2^{i}}\\
&=n \sum\limits_{i=0}^n \frac{1}{2^{i}}  (\log n - \log 2^{i})\\
&=n \sum\limits_{i=0}^n \frac{1}{2^{i}} \log n -  \sum\limits_{i=0}^n \frac{1}{2^{i}}  \log 2^{i}\\
&=n \sum\limits_{i=0}^n \frac{1}{2^{i}} \log n -  \sum\limits_{i=0}^n \frac{ \log 2^{i}}{2^{i}}\\
&=n \sum\limits_{i=0}^n \frac{1}{2^{i}} \log n -  d \sum\limits_{i=0}^n \frac{i}{2^{i}}\\
&=2 n  \log n - d \sum\limits_{i=0}^n \frac{i}{2^{i}}
\end{align}$$
I am still trying to figure out the sum of the second summation above but I somehow feel that it will be bigger than $2n \log n$ which makes my whole approach wrong. 
Is there another way to tackle this problem?  
 A: Consider the equality
$$
1+x+x^2+...+x^n=\frac{x^{n + 1} -1}{x-1}
$$
Differentiate it by $x$, then multiply by $x$:
$$
x+2x^2+3x^3+...+n x^n=\frac{nx^{n+2} - (n + 1)x^{n+1} + x}{(x-1)^2}
$$
Now we can substitute $x=\frac{1}{2}$ and obtain
$$
\sum\limits_{i=0}^n\frac{i}{2^i}=n\left(\frac{1}{2}\right)^{n} - (n + 1)\left(\frac{1}{2}\right)^{n-1} + 2
$$
A: Summary: Like in several questions of the same ilk asked previously on the site, the recursion can only determine each $T(n)$ as a function of $T(2i+1)$ and $k\geqslant0$, where $n=(2i+1)2^k$. Furthermoree, the series considered by the OP are simply not relevant to the asymptotics of $T(n)$. The growth of $T(n)$ of the order of $n\log n$, which the OP seems to infer, is not compatible with the recursion at hand since, speaking very roughly, $T(n)$ grows like $n^{\frac12\log n}$.
Gory details: Consider for example $t_k=T(2^k)$. Then, for every $k\geqslant1$, 
$$
t_k=2^{k-1}t_{k-1}+k\log2,
$$
hence the change of variables
$
s_k=2^{-k(k-1)/2}t_k
$
yields the recursion $s_0=t_0=T(1)$ and
$
s_k=s_{k-1}+2^{-k(k-1)/2}k\log2$. This is solved by
$$
s_k=s_0+\log2\sum\limits_{i=1}^ki2^{-i(i-1)/2},
$$
whose translation in terms of $t_k$ is
$$
t_k=2^{k(k-1)/2}\left(T(1)+\log2\sum\limits_{i=1}^k\frac{i}{2^{i(i-1)/2}}\right).
$$
Finally,
$$
T(2^k)=2^{k(k-1)/2}\tau_0-(\log2)\,(k/2^{k})+o(k/2^k),$$
with
$$
\tau_0=T(1)+(\log2)\,\sum\limits_{i=1}^{\infty}\frac{i}{2^{i(i-1)/2}}= T(1)+1.69306\ldots
$$
Conclusion: One sees that, along the subsequence indexed by the powers of $2$, $T(n)$ grows roughly like $n^{\frac12\log n}$ rather than like $n\log n$. The same argument applies to each subsequence indexed by the powers of $2$ times any given odd integer.
A: The summation 
$$ \sum\limits_{i=0}^n \frac{i}{2^{i}} $$
is equal to
$$ \sum\limits_{i=0}^n i(\frac{1}{2})^i $$
which is of the form 
$$ \sum\limits_{i=0}^n ix^i, x = \frac{1}{2} $$
Consider the summation $$ \sum\limits_{i=0}^n x^i = \frac{x^{n+1} - 1}{x - 1} $$
By differentiating with respect to $x$ we have 
$$ \frac{d}{dx}\left( \sum\limits_{i=0}^n x^i \right) = \frac{d}{dx} \left( \frac{x^{n+1} - 1}{x - 1} \right)$$
$$ \Rightarrow \sum\limits_{i=0}^n ix^{i-1}  =  \frac{(x - 1)(n + 1)x^n - (x^{n+1} -1)(1)}{(x - 1)^2} $$
$$ \Rightarrow \sum\limits_{i=0}^n ix^{i-1}  =  \frac{(x^{n+1} - x^n)(n + 1) - x^{n+1} + 1}{(x - 1)^2} $$
$$ \Rightarrow \sum\limits_{i=0}^n ix^{i-1}  =  \frac{(nx^{n+1} - nx^n) + (x^{n+1} - x^n) - x^{n+1} + 1}{(x - 1)^2} $$
$$ \Rightarrow \sum\limits_{i=0}^n ix^{i-1}  =  \frac{nx^{n+1} - nx^n + x^{n+1} - x^n - x^{n+1} + 1}{(x - 1)^2} $$
$$ \Rightarrow \sum\limits_{i=0}^n ix^{i-1}  =  \frac{nx^{n+1} - nx^n - x^n + 1}{(x - 1)^2} $$
By multiplying $x$ to both sides,
$$ x\sum\limits_{i=0}^n ix^{i-1}  =  x\left( \frac{nx^{n+1} - nx^n - x^n + 1}{(x - 1)^2} \right)$$
$$ \Rightarrow \sum\limits_{i=0}^n ix^{i}  =  \frac{nx^{n+2} - nx^{n+1} - x^{n+1} + x}{(x - 1)^2} $$
By substitution $ \left( x = \frac{1}{2} \right) $,
$$ \sum\limits_{i=0}^n i\left(\frac{1}{2}\right)^{i}  =  \frac{n\left(\frac{1}{2}\right)^{n+2} - n\left(\frac{1}{2}\right)^{n+1} - \left(\frac{1}{2}\right)^{n+1} + \left(\frac{1}{2}\right)}{(\left(\frac{1}{2}\right) - 1)^2} $$
$$ \Rightarrow \sum\limits_{i=0}^n i\left(\frac{1}{2}\right)^{i}  =  \frac{n\left(\frac{1}{2^{n+2}}\right) - n\left(\frac{1}{2^{n+1}}\right) - \left(\frac{1}{2^{n+1}}\right) + \left(\frac{1}{2}\right)}{\left(-\frac{1}{2}\right)^2} $$
$$ \Rightarrow \sum\limits_{i=0}^n i\left(\frac{1}{2}\right)^{i}  =  \frac{\frac{n}{2^{n+2}} - \frac{n + 1}{2^{n+1}} + \frac{1}{2}}{\left(\frac{1}{4}\right)} $$
$$ \Rightarrow \sum\limits_{i=0}^n i\left(\frac{1}{2}\right)^{i}  =  4 \left( \frac{n}{2^{n+2}} - \frac{n + 1}{2^{n+1}} + \frac{1}{2} \right) $$
$$ \Rightarrow \sum\limits_{i=0}^n i\left(\frac{1}{2}\right)^{i}  =  4 \left( \frac{n}{2^{n+2}} - \frac{2(n + 1)}{2^{n+2}} + \frac{2^{n+1}}{2^{n+2}} \right) $$
$$ \Rightarrow \sum\limits_{i=0}^n i\left(\frac{1}{2}\right)^{i}  =  \frac{n - 2(n + 1) + 2^{(n+1)}}{2^{n}} $$
$$ \Rightarrow \sum\limits_{i=0}^n \frac{i}{2^{i}} = \frac{n - 2(n + 1) + 2^{(n+1)}}{2^{n}} $$
