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)$.

a) rewriting the sum
First of all we have better to rewrite the sum as
$$
\eqalign{
  & S(n) = \sum\limits_{k = 1}^n {k\ln k\left( \matrix{
  n \cr   k \cr}  \right)}  = \sum\limits_{k = 1}^n {\ln \left( {k^k } \right)\left( \matrix{
  n \cr   k \cr}  \right)}  = \sum\limits_{k = 0}^n {\ln \left( {k^k } \right)\left( \matrix{
  n \cr   k \cr}  \right)}   \cr 
  &  = \sum\limits_{0 \le k} {k\ln \left( k \right)\left( \matrix{
  n \cr   k \cr}  \right)}  = n\sum\limits_{1 \le k} {\ln \left( k \right)\left( \matrix{
  n - 1 \cr   k - 1 \cr}  \right)}  = n\sum\limits_{0 \le k} {\ln \left( {1 + k} \right)\left( \matrix{
  n - 1 \cr   k \cr}  \right)}  =   \cr 
  &  = n\,R(n - 1) \cr} 
$$
where $R(n)$ is more manageable.
b) properties of R
(in the attempt to find a closed form or interesting identities)
One interesting property of $R$ is that the binomial inversion theorem tells
$$
R(n) = \sum\limits_{0 \le k} {\ln \left( {1 + k} \right)
\left( \matrix{  n \cr   k \cr}  \right)} \quad  \Leftrightarrow \quad \ln \left( {1 + n} \right)
 = \sum\limits_{0 \le k} {\left( { - 1} \right)^{n - k}
 \left( \matrix{  n \cr   k \cr}  \right)R(k)}  = \left. {\Delta ^n R(n)\;} \right|_{n = 0} 
$$
Another interesting fact is that we can rewrite $R$ as
$$
\eqalign{
  & R(n) = \sum\limits_{0 \le k} {\ln \left( {1 + k} \right)\left( \matrix{  n \cr 
  k \cr}  \right)}  = n!\sum\limits_{0 \le k} {{{\ln \left( {1 + k} \right)} \over {k!}}{1 \over {n - k}}}   \cr 
  & {{R(n)} \over {n!}} = \sum\limits_{0 \le k} {{{\ln \left( {1 + k} \right)} \over {k!}}{1 \over {n - k}}}  \cr} 
$$
and thus obtain the e.g.f.
$$
\eqalign{
  & F(z) = \sum\limits_{0 \le n} {{{R(n)} \over {n!}}z^n }
  = \sum\limits_{0 \le k} {{{\ln \left( {1 + k} \right)z^k } \over {k!}}{{z^{n - k} } \over {\left( {n - k} \right)!}}}  =   \cr 
  &  = \left( {\sum\limits_{0 \le k} {{{\ln \left( {1 + k} \right)} \over {k!}}z^k } } \right)
\left( {\sum\limits_{0 \le j} {{{z^j } \over {j!}}} } \right)
 = e^z \left( {\sum\limits_{0 \le k} {{{\ln \left( {1 + k} \right)} \over {k!}}z^k } } \right) \cr} 
$$
c) approximation
Since the binomial is symmetric wrt $n/2$ and the log
gets quite "flat" for large values of $k$, we have better
to center the approximation at $n/2$.
$$
\eqalign{
  & R(n) = \sum\limits_{0 \le k} {\ln \left( {1 + k} \right)
\left( \matrix{ n \cr  k \cr}  \right)}  = \sum\limits_{\left( { - \left\lfloor {n/2} \right\rfloor  \le } \right)
j\left( { \le \left\lfloor {n/2} \right\rfloor } \right)} {\ln \left( {1 + n/2 + j} \right)
\left( \matrix{ n \cr   n/2 + j \cr}  \right)}  =   \cr 
  &  = \sum\limits_{\left( { - \left\lfloor {n/2} \right\rfloor  \le } \right)j
\left( { \le \left\lfloor {n/2} \right\rfloor } \right)} {\left( {\ln \left( {1 + n/2} \right)
 + \ln \left( {1 + {j \over {\left( {1 + n/2} \right)}}} \right)} \right)
\left( \matrix{ n \cr  n/2 + j \cr}  \right)}  =   \cr 
  &  = \ln \left( {1 + n/2} \right)2^n  + \sum\limits_{\left( { - \left\lfloor {n/2} \right\rfloor  \le } \right)
j\left( { \le \left\lfloor {n/2} \right\rfloor } \right)} {\ln \left( {1 + {j \over {\left( {1 + n/2} \right)}}} \right)
\left( \matrix{ n \cr  n/2 + j \cr}  \right)}   \cr 
  &  \le \ln \left( {1 + n/2} \right)2^n  + {1 \over {\left( {1 + n/2} \right)}}
\sum\limits_{\left( { - \left\lfloor {n/2} \right\rfloor  \le } \right)j\left( { \le \left\lfloor {n/2} \right\rfloor } \right)}
 {j\left( \matrix{ n \cr   n/2 + j \cr}  \right)}  =   \cr 
  &  = \ln \left( {1 + n/2} \right)2^n  + {1 \over {\left( {1 + n/2} \right)}}
\sum\limits_{\left( { - \left\lfloor {n/2} \right\rfloor  \le } \right)j\left( { \le \left\lfloor {n/2} \right\rfloor } \right)}
 {\left( {j + n/2 - n/2} \right)\left( \matrix{n \cr  n/2 + j \cr}  \right)}  =   \cr 
  &  = \ln \left( {1 + n/2} \right)2^n  - {{n/2} \over {\left( {1 + n/2} \right)}}2^n
  + {1 \over {\left( {1 + n/2} \right)}}\sum\limits_{0 \le k}
 {k\left( \matrix{ n \cr  k \cr}  \right)}  =   \cr 
  &  = \ln \left( {1 + n/2} \right)2^n  \cr} 
$$
i.e.
$$
R(n) \le \ln \left( {1 + n/2} \right)2^n ,\quad
 S(n) \le n\ln \left( {1 + \left( {n - 1} \right)/2} \right)2^{n - 1} 
$$
and
$$
{{\ln \left( {1 + n/2} \right)2^n } \over {R(n)}}\;\mathop  \to \limits_{n \to \infty } \;1
$$
