18
$\begingroup$

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} $$

$\endgroup$
1

2 Answers 2

18
$\begingroup$

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*}

$\endgroup$
1
  • 1
    $\begingroup$ 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?. $\endgroup$
    – Wyvern666
    Jan 24, 2014 at 17:26
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ You should provide justification for the final step above in the form of a reference or theorem in order to render a proper proof. $\endgroup$
    – T.A.Tarbox
    Mar 31, 2017 at 0:41

Your Answer

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