Closed form of a logarithmic sum involving binomial coefficient

Question

I am trying to simplify an equation and in a term I have the following, $$\sum _{k=1}^n\binom{n}{k}k \log _2(k) $$ I was wondering if I can write above in closed form?

Answer 1

$$ S = \sum_{k=1}^n\binom{n}{k} k\, \log{k} \sim n\, 2^{n-1}\Big(\log{(n/2)} + \frac{1}{2n} + O\big(\frac{\log{n}}{n^2} \big) \Big)$$ Note the formula is stated in natural log, not 2-based log. Let's build some intuition before jumping in. By differentiation of the binomial theorem it is easy to show that $$ (1) \quad \quad \sum_{k=1}^n\binom{n}{k} k = n\, 2^{n-1} $$ Because $S$ is this with the addition of the 'slowly varying' $\log{k}$ and because all the terms in the summand are positive, we expect $S$ to look like $n\,2^{n-1}(\log(n)$ - 'correction' ) and the correction occurs because the terms earlier in the sum don't all have a $\log(n),$ but something less, multiplying them. (The correction is $\log(2)$ by comparing with the asymptotic formula.)

The method for deriving the asymptotic formula is simple in principal, depending on the Euler representation of the $\Gamma$ function and its first derivative, and the binomial theorem and its derivatives. We need $$(2) \quad \quad \int_0^\infty e^{-a\,t} t^{s-1} \log{t} \,dt = a^{-s}\big(-\log(a) + \psi(s)\,\big)\Gamma(s) $$ where $\psi(s)$ is the digamma function. In particular for $s=1, a=k,$ $$ \log{k} = -k \int_0^\infty e^{-k\,t} \log{t}\, dt - \gamma .$$ Insert the previous formula into the definition for $S$ to obtain $$S=-\gamma \, \sum_{k=1}^n\binom{n}{k} k - \int_0^\infty dt\,\log{t} \, \underbrace{\sum_{k=1}^n\binom{n}{k} k^2 e^{-k\,t} }_{:=U} .$$ The first term is solvable with (1). By twice differentiating the binomial theorem, $$U=n\, e^{-t}(1+e^{-t})^{n-2}(1+n\,e^{-t}) = 2^{n-2}\,n\,e^{-n\,t\,/2} \cosh^{n-2}(t/2)(1+n\,e^{-t})$$ where in the second step a hyp trig ID was used. As $n \to \infty, \, e^{-n\, t/2}$ crowds more and more into the space near $t=0$ while $\cosh(t=0) = 1.$ Thus we'll expand $\cosh$ as a power series, $$ \cosh^{n-2}(t/2) \sim 1 + \frac{n-2}{8}t^2 + O(n^2)t^4.$$ Plug into the integral we want to asymptotically estimate, $$V:=\int_0^\infty dt \log{t} \, U \sim n\,2^{n-2} \int_0^\infty dt \log{t} \, e^{-n\,t/2}\big(1+\frac{n-2}{8}t^2 + O(n^2)t^2\big)\big(1+n\, e^{-t}\big)$$ Without including the $O(n^2)t^4$ term, there are 4 terms. For each of those terms use equation (2). In detail, $$\frac{2^{-(n-2)}}{n}V=(n/2)^{-1}\big(-\log{(n/2)}+\psi(1)\big)+\frac{n-2}{8}(n/2)^{-3}\big(-\log{(n/2)} + \psi(3) \big)\Gamma(3)+ $$ $$+n(1+n/2)^{-1}\big(-\log{(1+n/2)}+\psi(1)\big)+\frac{n(n-2)}{8} (1+n/2)^{-3}\big(-\log{(1+n/2)}+\psi(3)\big)\Gamma(3)$$ Expand this mess in an asymptotic series for $n \to \infty.$ The question is, how many terms should be kept? From the dropped $O(n^2)t^4$ term, we can see that we get another $n$ from the $(1+n\,e^{-t})$ factor in the integrand, and a $n^{-5} \log{n}$ from the $t^4$ by again using eq (2). Thus we can't keep terms of $O(\log(n)/n^2)$ unless we explicitly do that dropped term arising from the $\cosh.$ The equation at the top of the answer is the result of truncating this expansion as required, and doing some algebra. For numerical comparison, by defining the relative percent error as 100*(true - asym)/true, for $n=10$ the error is only 0.18% and for $n=40,$ .0054%.