13
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\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$
    – Martin Sleziak
    Commented Mar 4, 2013 at 11:44
  • $\begingroup$ I'll add a link to another question, where a combinatorial proof is given. $\endgroup$
    – Martin Sleziak
    Commented Mar 4, 2013 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$
    – Marc van Leeuwen
    Commented Mar 5, 2013 at 11:00

2 Answers 2

Reset to default
7
$\begingroup$

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.

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

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .