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