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: 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$.
A: 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
$$
A: User @runway44 already showed that
$$ \sum_{k=1}^{n} (k \log k) \binom{n}{k} \leq n2^{n-1}\log n.$$
To show that this upper bound is "sharp", note that the function
$$ f(x) = \begin{cases}
x \log x, & x > 0 \\
0, & x = 0
\end{cases} $$
is continuous and convex on $[0, \infty)$. So, if $X \sim \operatorname{Binomial}(n, \frac{1}{2})$, then by the Jensen's inequality,
$$ \sum_{k=1}^{n} (k \log k) \binom{n}{k}
= 2^n \mathbf{E}[f(X)]
\geq  2^n f(\mathbf{E}[X])
= n2^{n-1}\log\left(\frac{n}{2}\right). $$

Addendum. We also have the integral representation
$$ \sum_{k=1}^{n} (k \log k) \binom{n}{k} = n2^{n-1} \int_{0}^{1} \frac{1 - (\frac{1+x}{2})^{n-1}}{\log(1/x)} \, \mathrm{d}x. $$
Analyzing this integral might possibly allow us to extract more terms in the asymptotic expansion, but let me leave this to others.
