Vandermonde's Identity

Vandermonde's identity (or Vandermonde's convolution), named after Alexandre-Théophile Vandermonde, states that any combination of $k$ objects from a group of $(m+n)$ objects must have some $0\ \leq\ r\ \leq\ k$ objects from a group of $m$ objects and the remaining $(k-r)$ objects from a group of $n$.

Mathematically, $${m+n \choose k} = \sum_{r=0}^k {m \choose r}{n \choose k-r}.$$ This identity can be useful when evaluating certain other sums, or doing difficult combinatorics problems.

We consider the binomial expansion of $(1+x)^{m+n}$

$$(1+x)^{m+n} = \sum_{k=0}^{m+n} {m+n \choose k}x^k.$$

Also, notice that, we can consider the expansion by observing that $(1+x)^{m+n} = (1+x)^m(1+x)^n:$

$$\begin{aligned} (1+x)^{m+n} & = (1+x)^{m}(1+x)^{n} \\ & = \left(\sum_{i=0}^m {m \choose i} x^i\right)\left(\sum_{j=0}^n {n \choose j} x^j\right) \\ & = \left({m \choose 0}+{m \choose 1}x+{m \choose 2}x^2+\cdots \right) \times \left({n \choose 0}+{n \choose 1}x+{n \choose 2}x^2+\cdots\right) \\ & = \left({m \choose 0}{n \choose 0}\right)x^0 +\left({m \choose 0}{n \choose 1}+{m \choose 1}{n \choose 0}\right)x +\left({m \choose 0}{n \choose 2}+{m \choose 1}{n \choose 1}+{m \choose 2}{n \choose 0}\right)x^2+\cdots. \end{aligned}$$

Thus, we can conclude that the coefficient of $x^k$ in the above expansion is

$${m \choose 0}{n \choose k}+{m \choose 1}{n \choose k-1}+\cdots+{m \choose k}{n \choose 0} = \sum_{r=0}^k {m \choose r}{n \choose k-r}.$$

Therefore, by comparing the coefficients of $x^k$

$$\sum_{r=0}^k {m \choose r}{n \choose k-r} = {m+n \choose k}.\ _\square$$

Note: In particular, Vandermonde's identity holds for all binomial coefficients, not just the non-negative integers that are assumed in the combinatorial proof.

Suppose there are $m$ boys and $n$ girls in a class and you're asked to form a team of $k$ pupils out of these $m+n$ students, with $0 \le k \le m+n.$ You can do this in ${m+n \choose k}$ ways. But, now we count in rather a different manner. To form the team, you can choose $i$ boys and $k-i$ girls for some fixed $i$. There are ${m \choose i}{n \choose k-i}$ ways to do this. Now, either you can have $0$ boys and $k$ girls, or $1$ boy and $k-1$ girls, or $2$ boys and $k-2$ girls, or $\ldots$. That is, there are $\sum_{r=0}^k {m \choose r}{n \choose k-r}$ ways to form the team.

Thus, we derive at our result

$$\sum_{r=0}^k {m \choose r}{n \choose k-r} = {m+n \choose k}.$$

Prove

$${2n \choose n} = \sum_{r=0}^n {n \choose r}^2.$$

---

The above sum is a special case of Vandermonde's identity where $m=k=n.$

Thus, we get

$${n+n \choose n} = \sum_{r=0}^n {n \choose r}{n \choose n-r}.$$

Therefore, because of the identity ${n \choose n-r}={n \choose r}$, we get

$${2n \choose n} = \sum_{r=0}^n {n \choose r}^2.\ _\square$$

I'll leave the combinatorial proof of this identity as an exercise for you to work out.

In the algebraic proof of the above identity, we multiplied out two polynomials to get our desired sum. Similarly, by multiplying out $p$ polynomials, you can get the generalized version of the identity, which is

$$\sum_{k_1+\dots +k_p = m}^m {n\choose k_1} {n\choose k_2} {n\choose k_3} \cdots {n \choose k_p} = { pn \choose m}.$$

You can also think of it combinatorially, by considering $p$ bags with each bag consisting of $n$ balls. Thus, you have a total of $pn$ balls. Now you need to pick up $m$ balls in total. There are

$${pn \choose m}$$

ways to do it.

On a similar argument as stated above, we can also pick up $m$ balls by picking $i_1$ balls from bag #1, $i_2$ balls from bag #2, ..., and $i_p$ balls from bag #p. Thus for a fixed set of $(i_1,i_2,\ldots,i_p)$, there are ${n\choose k_1} {n\choose k_2} {n\choose k_3} \cdots {n \choose k_p}$ ways to do it, and hence in total

$$\sum_{k_1+\dots +k_p = m}^m {n\choose k_1} {n\choose k_2} {n\choose k_3} \cdots {n \choose k_p}$$

ways.

This leads us to our desired result

$$\sum_{k_1+\dots +k_p = m}^m {n\choose k_1} {n\choose k_2} {n\choose k_3} \cdots {n \choose k_p} = { pn \choose m}.\ _\square$$

Moving the LHS (in Vandermonde's identity) to RHS in the denominator yields

$$\begin{aligned} 1 & = & \frac{\sum_{r=0}^k {m \choose r}{n \choose k-r}}{{m+n \choose k}} \\ & = & \sum_{r=0}^k \frac{{m \choose r}{n \choose k-r}}{{m+n \choose k}} \\ & = & \frac{{m \choose 0}{n \choose k}}{{m+n \choose k}}+\frac{{m \choose 1}{n \choose k-1}}{{m+n \choose k}}+\frac{{m \choose 2}{n \choose k-2}}{{m+n \choose k}}+\cdots . \end{aligned}$$

Each term in the above sum can be interpreted as a probability, that is, the probability distribution of the number of blue balls in $k$ draws without replacement from a bag containing $n$ blue and $m$ green balls. The resulting distribution is better known as hypergeometric probability distribution.

Chu-Vandermonde's Identity:

The identity was extended to non-integer arguments, by Wenchang Chu, and is known by the name Chu-Vandermonde Identity, which is stated as follows:

For general complex-valued $x$ and $y$ and any non-negative integer $n$, it takes the form $${x+y \choose n}=\sum_{k=0}^n {x \choose k}{y \choose n-k}.$$ It can be re-written in terms of falling Pochhammer symbol as $$(x+y)_n = \sum_{k=0}^n {n \choose k} (x)_k (y)_{n-k} ,$$ where $(x)_{k}=x(x-1)(x-2)\ldots(x-k+1)$ and is known as the falling Pochhammer symbol (or descending factorial).

Rothe-Hagen Identity:

The Rothe-Hagen identity, named after Heinrich August Rothe and Johann Georg Hagen, is a further generalization of Vandermonde's identity, which extends for all complex numbers $(a,b,c)$. It states that

$$\sum_{k=0}^n\frac{a}{a+bk}{a+bk \choose k}{c-bk \choose n-k}={a+c \choose n}.$$

Try the following problems: