# Closed form for $\sum_{k=0}^{n} k\binom{n}{k}\log\binom{n}{k}$

Is it possible to write this in closed form: $$\sum_{k=0}^{n} k\binom{n}{k}\log\left(\vphantom{\Huge A}\binom{n}{k}\right)$$

Can you get something like $$n2^{n-1}\log(2^{n-1})$$

-
Originally, I was trying to use the fact that $$log(n!) = \Theta(nlogn)$$ and the definition of $$\binom{n}{k}$$ to prove a lower bound of this form. It got a bit messy. –  rhl Mar 18 '13 at 1:59
Are you after a closed form (probably non existent) or a lower bound or an upper bound? –  Did Mar 19 '13 at 6:24

Warning!

I couldn't find a closed form. An approximation is described below.

You may start by symmetrizing the summand to get $$\sum_{k=0}^{n} k\binom{n}{k}\log\binom{n}{k}={n\over 2}\sum_{k=0}^{n} \binom{n}{k}\log\binom{n}{k}.\tag1$$

The terms in the sum on the right hand side of (1) are symmetric around $n/2$ and concentrated near $k\approx n/2$, so replacing $\log{n\choose k}$ with $\log{n\choose n/2}$ gives a reasonable approximation, and an upper bound. That is, $${n\over 2}\sum_{k=0}^{n} \binom{n}{k}\log\binom{n}{k}\approx {n\over 2}\,2^n\log{n\choose n/2}.$$

Using Stirling's formula gives another approximation (and upper bound) $${n\over 2} \sum_{k=0}^{n} \binom{n}{k}\log\binom{n}{k}\approx {n\over 2}\,2^n [(n+1/2)\log(2)-\log(n\pi)/2].$$

Added: A better approximation results by replacing $\log{n\choose k}$ with $\log{n\choose n/2}-{2\over n}(k-n/2)^2$. With a little work you can get $${n\over 2}\,\sum_{k=0}^{n} \binom{n}{k}\log\binom{n}{k}={n\over 2}\,2^n \left[\log{n\choose n/2}-{1\over 2}+o(1)\right].$$

-
This agrees to $O(2^n n)$ with the result I got by a similar method, $\sum_{k=0}^{n} k\binom{n}{k}\log\binom{n}{k}\sim 2^{n-1} n \log \left(2^n \sqrt{\frac{2}{n \pi e}}\right)$. (+1) –  user26872 Mar 25 '13 at 3:22
@oen Thanks. I think my argument could be made more formal by using Laplace's method for sums, but I was too lazy to chase down all the details. –  Byron Schmuland Mar 25 '13 at 3:29
The question asks for a closed form, though no? –  Mariano Suárez-Alvarez Mar 25 '13 at 18:14
Mariano Quite right! I couldn't find a closed form, so I decided to look for an approximation. Maybe this will be useful to someone.... –  Byron Schmuland Mar 25 '13 at 18:28

If $f(n)$ is your sum, then $e^{f(n)}$ becomes an integer product, say $p(n)$, formed by multiplying each binomial coefficient $\binom{n}{k}$ to the power $k \cdot \binom{n}{k}.$ That is, $$p(n)=e^{f(n)}=\prod_{k=0}^n \binom{n}{k}^{k \binom{n}{k}}.$$ The first few terms are $$p(1)=1,\ p(2)=2^2,\ p(3)=3^9,\ p(4)=2^{44}3^{12},\ p(5)=2^{50}5^{75}.$$ When I put the first three into o.e.i.s there was a hit, but it wasn't this sequence, as discovered when I tried the first four terms. (This is no argument that there is not a closed form, of course.)

One thing that initially seems to go against a closed form is that the primes entering into the log terms in $f(n)$ are the set of primes dividing binomial coefficients in row $n$ of the binomial triangle, and such primes don't seem to appear in any regular way from row to row, and it seems such lists become arbitrarily long as $n$ increases; at least one can say that in row $n=p$ the prime $p$ will appear.

-

THIS IS PART OF THE ANSWER: Ok since $$\binom{n}{k} = \binom{n}{n-k}$$ then we can large index terms with small index terms:

so: $$\sum_{k=0}^{n} k\binom{n}{k}\log{\binom{n}{k}} = \sum_{k=0}^{n/2}(k \binom{n}{k}\log{\binom{n}{k}} + (n-k)\binom{n}{n-k}\log{\binom{n}{n-k}}) = \sum_{k=0}^{n/2}n\binom{n}{k}\log{\binom{n}{k}} = n\sum_{k=0}^{n/2}\binom{n}{k}\log{\binom{n}{k}}$$

Now we just need to show the rest is bounded by $$2^{n-1}\log(2^{n-1})$$

-