I would like to prove inductively that $${2n\choose n}=\sum_{i=0}^n{n\choose i}^2.$$

I know a couple of non-inductive proofs, but I can't do it this way. The inductive step eludes me. I tried naively things like $${2n+2\choose n+1}={2n+2\over n+1}{2n+1\choose n}=2\cdot {2n+1\over n+1}{2n\choose n},$$

But I don't think it can lead me anywhere. I would like the proof to be as simple as possible.

  • 1
    $\begingroup$ This is a special case of Chu-Vandermonde identity. Sometimes a proof by induction might be easier if you prove a more general result. Although I am not sure whether it helps in this case. $\endgroup$ Mar 4 '13 at 11:44
  • $\begingroup$ I'll add a link to another question, where a combinatorial proof is given. $\endgroup$ Mar 4 '13 at 11:48
  • $\begingroup$ This result is formulated too narrowly to have much chance of a inductive proof: knowing something about just the central binomial coefficients is insufficient in the induction because you don't have a useful recurrence realtion for just the central binomial coefficients. However, proving as Martin Sleziak suggested Chu-Vandermonde by induction (using Pascal's recurence) is a piece of cake. $\endgroup$ Mar 5 '13 at 11:00

Split the $2n$ elements into two groups of size $n$ Then the no. of ways of choosing $n$ from the $2n$ is the no. of ways of choosing $i$ from the 1st and $n-i$ from the 2nd and letting $i$ vary.

  • 11
    $\begingroup$ How is this an inductive proof? $\endgroup$
    – Bartek
    Mar 4 '13 at 11:59

After Martin Sleziak and Marc van Leeuwen's comments, I've found this inductive proof of Vandermonde's identity. (On this very site.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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