What is $\sum_{k = 1}^n (k \log k)\binom{n}{k}$? If the exact answer is difficult to find, what is the tightest asymptotic upper bound? While trying to solve the complexity of my program I came across the the following summation:
$$\sum_{k = 1}^n (k \log k)\binom{n}{k}$$
Could you please provide a solution to this sum. If it is difficult to obtain the exact solution, could you please provide an asymptotic upper bound that is as close as possible?
I was able to obtain the following asymptotic upperbound:
\begin{align*}
\sum_{k = 1}^n (k \log k)\binom{n}{k}
&= \mathop{O}\left(\sum k(k-1) \binom{n}{k} \right) \\
&= \mathop{O}\left(\sum n(n-1) \binom{n-2}{k-2} \right) \\
&= \mathop{O}\left(n^2 \sum \binom{n-2}{k-2} \right) \\
&= \mathop{O}(n^2 2^n)
\end{align*}
Is it possible to get smaller upper bound, for example $O(2^n n \log n)$.

If we write $(1+x)^n=\sum\limits_{k=0}^n\binom{n}{k}x^k$, differentiate, and evaluate at $x=1$, we get the lower bound
$$ \sum_{k=0}^n k\binom{n}{k}=n2^{n-1}. $$
If we also use $\log k\le \log n$, we get the upper bound of $n2^{n-1}\log n$.
