Vandermonde’s Identity from the Generalized Product Rule

Vandermonde’s Identity, \displaystyle \sum_{k=0}^r \binom{n}{k} \binom{m}{r-k} = \binom{n+m}{r}, is one of the more famous identities involving the binomial coefficients.  A standard way to prove it is with the following combinatorial argument.

How many ways are there to choose a committee of size r from a group of n men and m women?  By definition of the binomial coefficient, the answer is \binom{n+m}{r}.  Alternatively, condition on the number k of men on the committee.  There are \binom{n}{k} ways to choose the men, and then there are \binom{m}{r-k} ways to choose the remaining r-k members of the committee from the m women.  Summing over all possible values of k gives the left side.

In this post we’re going to give a much less standard proof of Vandermonde’s Identity — one via the generalized product rule for derivatives.  In addition, while the combinatorial proof requires n and m to be natural numbers, our proof holds for all real numbers.

The generalized product rule, sometimes known as Leibniz’s Generalized Rule, gives a formula for the nth derivative of the product of two functions.  Here it is:

\displaystyle (fg)^{(n)}(x) = \sum_{k=0}^n \binom{n}{k} f^{(k)}(x) g^{(n-k)}(x).

This formula can be easily proved by induction.

Let f(x) = x^n, and let g(x) = x^m.  We know that the rth derivative of a power function like x^n is n^{\underline{r}} x^{n-r}, where n^{\underline{r}} is the falling factorial n(n-1) \cdots (n-r+1).  Now, let’s look at the rth derivative of f(x) g(x) = x^{n+m}.  As we just argued, this is (n+m)^{\underline{r}} x^{n+m-r}.  By the generalized product rule, then, we have

\displaystyle (n+m)^{\underline{r}} x^{n+m-r} = \sum_{k=0}^r \binom{r}{k} n^{\underline{k}} x^{n-k} m^{\underline{r-k}} x^{m-r+k}

\displaystyle \implies (n+m)^{\underline{r}} x^{n+m-r} = \sum_{k=0}^r \frac{r!}{(r-k)! k!} n^{\underline{k}} m^{\underline{r-k}} x^{n+m-r}

\displaystyle \implies \frac{(n+m)^{\underline{r}}}{r!} x^{n+m-r} = \left(\sum_{k=0}^r \frac{n^{\underline{k}}}{k!} \frac{m^{\underline{r-k}}}{(r-k)!}\right) x^{n+m-r}.

The coefficients of the two expressions here must be equal in order for the expressions themselves to be equal.  In addition, using the definition of the generalized binomial coefficient, we have \binom{n}{k} = \frac{n^{\underline{k}}}{k!}.  (This allows binomial coefficients to be defined for values of n that are not natural numbers.)  All of this gives us Vandermonde’s Identity,

\displaystyle \binom{n+m}{r} = \sum_{k=0}^r \binom{n}{k} \binom{m}{r-k}.

Advertisements
This entry was posted in binomial coefficients, calculus, combinatorics. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s