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

• Isn't $\sum_{k=2}^n\binom nk=2^n-1-n$ a very simple lower bound for your sum? It couldn't possibly be $O(n^2)$ then. I think you meant $O(n^22^n)$. Commented Jun 3, 2022 at 10:09
• @Arthur Thank you! Yes, I forgot the $2^n$ part. Commented Jun 3, 2022 at 11:15
• A general statement: $\displaystyle \sum_{k = 1}^n f(n)\binom{n}{k}\sim 2^nf\Big(\frac{n}{2}\Big)$ at $n\to\infty$, where $f(x)$ is a smooth continuous function, growing (declining) not too fast (for example, as a polynomial) Commented Jun 4, 2022 at 1:20

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.

• Based on your integral, using an awkward method, I found $$\sum\limits_{k = 1}^n {(k\log k)\binom{n}{k}} \sim n2^{n - 1} \left( {\log \left( {\frac{n}{2}} \right) + \frac{1}{{2n}} + \frac{1}{{4n^2 }} + \frac{1}{{3n^3 }} + \frac{7}{{8n^4 }} + \frac{{53}}{{15n^5 }} + \frac{{77}}{{4n^6 }} + \frac{{925}}{{7n^7 }} + \ldots } \right)$$ as $n\to +\infty$.
– Gary
Commented Jun 3, 2022 at 13:37
• Indeed, using $\displaystyle\ln k=\int_0^\infty\frac{e^{-t}-e^{-kt}}{t}dt$ and $\displaystyle k=\frac{d}{dx}x^k\Big|_{x=1}$ $\displaystyle\sum\limits_{k = 1}^n {(k\log k)\binom{n}{k}}=\frac{d}{dx}\int_0^\infty\frac{dt}{t}\Big(e^{-t}(1+x)^n-\sum\limits_{k = 1}^n\binom{n}{k}x^ke^{-kt}\Big)\Big|_{x=1}$ $\displaystyle=n\int_0^\infty\Big(2^{n-1}-(1+e^{-t})^{n-1}\Big)\frac{e^{-t}}{t}dt$ Commented Jun 3, 2022 at 13:58

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