Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

Thanks.

share|improve this question
4  
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

3 Answers 3

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|improve this answer
1  
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

http://www.math.upenn.edu/~wilf/AeqB.html

share|improve this answer

I suggest you take a look on hypergeometric series.

share|improve this answer

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.