# 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\binom{n}{k}$$

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 at 1:59

2
Are you after a closed form (probably non existent) or a lower bound or an upper bound? – Did Mar 19 at 6:24

## 3 Answers

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) – oen Mar 25 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 at 3:29
The question asks for a closed form, though no? – Mariano Suárez-Alvarez♦ Mar 25 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 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})$$

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 19, "mathjax_display_tex": 13, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9641841053962708, "perplexity_flag": "head"}