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} $$
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*}
Other option is an analogy with the binomial identity:
$(x + y)^n = \sum_{k=0}^n \binom{n}{k} x^{n-k} . y^k $
In the following manner:
$$ \binom{m+n}r = \sum_{k=0}^r \binom mk \binom n{r-k} $$ $$\binom{m+n}r = \frac{(m+n)!}{r! ((m+n) - r)!} = \frac{1}{r!}.\frac{(m+n)!}{((m+n) - r)!} = \frac{1}{r!}.(m+n)^{\underline r} $$
See falling factorial power where
$(y)^{\underline k}=\underbrace{y(y-1)(y-2)\ldots(y-k+1)}_{k\text{ factors}} = \frac{y!}{(y-n)!}$
$$\binom mk \binom n{r-k}= \frac{m!}{k! (m- k)!}. \frac{n!}{(r-k)!.(n - (r-k))!} =$$ $$ \frac{1}{k!}. \frac{m!}{(m- k)!}.\frac{1}{(r-k)!}. \frac{n!}{(n - (r-k))!} = $$ $$ \frac{1}{k!}.m^{\underline{k}} .\frac{1}{(r-k)!}. n^{\underline{(r- k)}} = $$ $$ \frac{1}{k!(r-k)!}.m^{\underline{k}} . n^{\underline{(r- k)}} = $$ $$\sum_{k=0}^r \binom mk \binom n{r-k} = \sum_{k=0}^r \binom{r}{k}.m^{\underline{k}} . n^{\underline{(r- k)}} = (m+n)^{\underline r}$$
Now you can the formula by induction prove just as the Binomial Theorem
