# 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 group of \(n\).

Mathematically, \[{m+n \choose k} = \sum_{r=0}^k {m \choose r}{n \choose k-r}\]

#### Contents

## Algebraic Proof

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{eqnarray} (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+\ldots \right) \\ & & \qquad \times \left({n \choose 0}+{n \choose 1}x+{n \choose 2}x^2+\ldots\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+\ldots \\ \end{eqnarray} \] 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}+\ldots+{m \choose k}{n \choose 0} = \sum_{r=0}^k {m \choose r}{n \choose k-r}\]

And therefore, by comparing the coefficients of \(x^k\) \[\sum_{r=0}^k {m \choose r}{n \choose k-r} = {m+n \choose k}\]

## 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. You can do it 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\) boys 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.

And 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\]

\(\textbf{Solution.}\) 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}\]

And therefore, because of the identity \({n \choose n-r}={n \choose r}\), we get

\[\Rightarrow {2n \choose n} = \sum_{r=0}^n {n \choose r}^2\]

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

## Generalized Vandermonde's Identity

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, ... \(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 of \[\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}\]

## Hypergeometric Probability Distribution

Moving the LHS (in Vandermonde's Identity) to RHS, in the denominator yields \[\begin{eqnarray} 1 & = & \frac{\sum_{r=0}^k {m \choose r}{n \choose k-r}}{{m+n \choose k}} \nonumber \\ & = & \sum_{r=0}^k \frac{{m \choose r}{n \choose k-r}}{{m+n \choose k}} \nonumber \\ & = & \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}}+\ldots \nonumber \\ \end{eqnarray}\] Each term in the above sum can be interpreted as as probability, that is the probability distribution of number of the number of blue balls in \(k\) draws without replacement from a bag containing \(n\) blue and \(m\) green balls. And thus, the resulting distribution is better known as Hypergeometric Probability Distribution.

## Further Extensions

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

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)\cdots(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}.\]

## Problem Solving

Try the following problems.

As the well known song goes, on the first day of christmas my true love gave to me a partridge in a pear tree. On the second day of Christmas my true love gave to me 2 turtle doves and a partridge in a pear tree. On day *n* she gives me 1 of something, 2 of something else, ... , *n* of something else. At the end of the first 16 days how many gifts has my true love given to me in total?

At Peter's school, to progress to the next year he has to pass an exam every summer. Every exam is out of 50 and the pass mark is always 25. To graduate from school, he must pass 10 exams. Since Peter's work ethic increases with age, his scores never decrease.

Let \(N\) be the number of different series of marks Peter could have achieved, given that he left school without ever failing an exam. What are the last 3 digits of \(N\)?

**Cite as:**Vandermonde's Identity.

*Brilliant.org*. Retrieved from https://brilliant.org/wiki/vandermondes-identity/