2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ No, but an asymptotic formula for $n \to \infty$ is not too difficult to derive. If you want an asymptotic formula, say so, and I can type in a solution tomorrow, if someone else doesn't do it first. $\endgroup$ – skbmoore Aug 15 '18 at 22:56
  • $\begingroup$ @skbmoore An asymptotic formula would be appreciated. Thank you. $\endgroup$ – Wiliam Aug 16 '18 at 13:25
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks a lot for this, works amazingly good. Just can you please expand a little how to go from the last Eq to the very top one (result). $\endgroup$ – Wiliam Aug 17 '18 at 14:10
  • 1
    $\begingroup$ pseudocode in Mathematica: Series[ right-hand side last equation,{n,Infinity,2}]. Truncate as mentioned, and do a little simplifying by hand. $\endgroup$ – skbmoore Aug 19 '18 at 23:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.