Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
3  
Are you after a closed form (probably non existent) or a lower bound or an upper bound? –  Did Mar 19 '13 at 6:24
add comment

3 Answers

up vote 2 down vote accepted

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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