Vandermonde's Identity

# Vandermonde's Identity

We will now look at a very important binomial coefficient identity known as Vandermonde's identity which is state below.

 Theorem 1 (Vandermonde's Identity): If $m$, $n$, and $k$ are nonnegative integers such that $0 \leq k \leq (m + n)$ then $\displaystyle{\binom{m + n}{k} = \sum_{j=0}^{k} \binom{m}{j} \cdot \binom{n}{k-j}}$.
• Proof: The binomial coefficient $\binom{m + n}{k}$ says that out of $m + n$ objects we choose $k$ and $\binom{m + n}{k}$ is the number of ways we can choose this way. The righthand side of the equation sums up the number of ways that out of $m$ objects we choose $0$, $1$, …, $k$ alongside the number of ways that out of $n$ objects we choose $k$, $k - 1$, …, $1$, or $0$ correspondingly. The lefthand side therefore counts the same as the righthand side and so:
(1)
\begin{align} \quad \binom{m + n}{k} = \sum_{j=0}^{k} \binom{m}{j} \cdot \binom{n}{k - j} \quad \blacksquare \end{align}

For example, suppose that we want to compute $\binom{10}{3}$. We can rewrite this as $\binom{5 + 5}{3}$ and apply Vandermonde's identity to get:

(2)
\begin{align} \quad \binom{10}{3} = \binom{5 + 5}{3} = \sum_{j=0}^{3} \binom{5}{j} \cdot \binom{5}{3 - j} = \binom{5}{0} \cdot \binom{5}{3} + \binom{5}{1} \cdot \binom{5}{2} + \binom{5}{2} \cdot \binom{5}{1} + \binom{5}{3} \cdot \binom{5}{0} = 1 \cdot 10 + 5 \cdot 10 + 10 \cdot 5 + 10 \cdot 1 = 120 \end{align}
 Corollary 1: If $n$ is a nonnegative integer then $\sum_{j=0}^{n} \binom{n}{j}^2 = \binom{2n}{n}$.
• Proof: In Theorem 1 above let $m = n$ and let $k = n$. Then we get:
(3)
\begin{align} \quad \binom{m + n}{k} = \binom{n + n}{n} = \binom{2n}{n} = \sum_{j=0}^{n} \binom{n}{j} \cdot \binom{n}{n - j} \end{align}
• Applying the identity that $\binom{n}{n - j} = \binom{n}{j}$ and we get:
(4)