MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Does anyone know how to show the following combinatorial equality, $\sum_{i=0}^{n}\left(n-i\right)^{2}\binom{2n}{i}=n\cdot4^{n-1}$?

By the way, this is not a homework problem, otherwise one would be able to search the answer.


share|cite|improve this question
As Robin Chapman mentions, your sum is half of the full sum $\sum_{i=0}^{2n}(n-i)^2\dbinom{2n}i$. Note that $\sum_{i=0}^{2n}\dbinom{2n}ix^i=(1+x)^{2n}$ and if you aplly the differential operator $x\dfrac{d}{dx}$, you also have the closed formulas for $\sum_{i=0}^{2n}i^l\dbinom{2n}ix^i$ with $l=1,2$. A linear combination of the three will allow you to compute your expression. It's a homework problem! – Wadim Zudilin May 23 '10 at 9:50

It's half the sum of the same thing from $0$ to $2n$, which in turn is easily related to the variance of the number of heads in a sequence of $2n$ tosses of a fair coin.

share|cite|improve this answer
Robin, I spent time following your combinatorial hint. If the author claims that his problem isn't a homework, your combinatorial solution is definitely best possible. +1 – Wadim Zudilin May 23 '10 at 11:59

Try the Wilf-Zeilberger method and its friends. This automatically proves many such (hypergeometric) identities. See the book A = B

share|cite|improve this answer

I suggest you take a look on hypergeometric series.

share|cite|improve this answer

Your Answer


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.