Take the 2-minute tour ×

I am reading up on Vandermonde's Identity, and so far I have found proofs for the identity using combinatorics, sets, and other methods. However, I am trying to find a proof that utilizes mathematical induction. Does anyone know of such a proof?

For those who don't know Vandermonde's Identity, here it is:

For every $m \ge 0$, and every $0 \le r \le m$, if $r \le n$, then

$$ \binom{m+n}r = \sum_{k=0}^r \binom mk \binom n{r-k} $$

share|improve this question

1 Answer 1

up vote 10 down vote accepted

We have using the recursion formula for binomial coefficients the following for the induction step \begin{align*} \binom{m + (n+1)}r &= \binom{m+n}r + \binom{m+n}{r-1}\\ &= \sum_{k=0}^r \binom mk\binom n{r-k} + \sum_{k=0}^{r-1} \binom mk\binom{n}{r-1-k}\\ &= \binom mr + \sum_{k=0}^{r-1} \binom mk\biggl(\binom n{r-k} + \binom n{r-1-k}\biggr)\\ &= \binom mr\binom{n+1}0 + \sum_{k=0}^{r-1} \binom mk\binom{n+1}{r-k}\\ &= \sum_{k=0}^r \binom mk \binom{n+1}{r-k} \end{align*}

share|improve this answer
The induction could be donde over r?. Also, suppose we talk about the general version of this identity, with m and n possibly complex values, and r integer. We can do an induction proof over r?. –  Wyvern666 Jan 24 '14 at 17:26

Your Answer


