Combinatorial Identities

$\binom{n}{k}$ counts the ways to choose $k$ objects from $n$ objects. $\binom{n}{n-k}$ counts the ways to choose the $n-k$ objects you don't take. Every choice of what to take is exactly one choice of what to leave, so the two counts must be equal!

We use double counting: count one thing in two ways.

How many ways are there to select some subset of $n$ objects? For each object we have 2 choices: choose it or don't. So there are $2^n$ ways.

How many ways are there to select 0 objects? 1 object? 2 objects? $n$ objects? There are $\binom{n}{0}$ ways to select 0 objects, $\binom{n}{1}$ ways to select 1, $\binom{n}{2}$ ways to select 2, …, $\binom{n}{n}$ ways to select $n$.

Adding these up counts every subset once, by its size:

which must equal $2^n$!

Suppose we have $n$ students, and we must select some of them to go on a field trip.

One of the students, Bob, is sick and can't go. Among all subsets of the other $n - 1$ students, say $a$ have an even number of people and $b$ have an odd number.

Later, Bob recovers and can go. In terms of $a$ and $b$, how many subsets of all $n$ people are odd, and how many are even? Adding Bob to a group flips its parity. The $a$ even groups become odd, and the $b$ odd groups become even. Without Bob, they stay as they were.

In total, among all subsets of the $n$ people, how many are odd and how many are even? Odd: $b$ (without Bob) $+\ a$ (with Bob) $= a + b$. Even: $a + b$ too. They are the same!

What is this statement in terms of choose symbols? The odd groups number $\binom{n}{1} + \binom{n}{3} + \cdots$ and the even groups $\binom{n}{0} + \binom{n}{2} + \cdots$. These are equal, which is the identity.

Imagine you have $m$ oranges and $n$ bananas.

How many ways are there to select any $r$ fruits? There are $\binom{m+n}{r}$ ways.

How many ways are there to select $r$ oranges? From the $m$ oranges there are $\binom{m}{r}$ ways.

How many ways are there to select $r - 1$ oranges and 1 banana? $\binom{m}{r-1}$ ways for the oranges and $\binom{n}{1}$ for the banana: $\binom{m}{r-1}\binom{n}{1}$ in all.

Using this logic, can you find another formula for the number of ways to select $r$ fruits? The pick has $r$ oranges and 0 bananas, or $r-1$ oranges and 1 banana, …, or 0 oranges and $r$ bananas. Adding the cases:

But $\binom{m+n}{r}$ also counts the ways to choose $r$ fruits, so these must be equal!

What happens if you put $m = n = r = k$ in Vandermonde's Identity? You get

Why is each term a square? By symmetry (Theorem 6.1.1), $\binom{k}{k-i} = \binom{k}{i}$. So each term is $\binom{k}{i}^2$.

In words: choose $k$ people from $k$ red-shirts and $k$ blue-shirts. With $i$ reds you take $k - i$ blues, which is the same as choosing the $i$ blues to leave out.

Imagine you have $n + 1$ people and you must choose $r + 1$ leaders.

How many ways are there to do this? This is just $\binom{n+1}{r+1}$.

If Bob, one of the $n + 1$ people, is a leader, how many ways are there to choose the other $r$ leaders from the remaining $n$ people? This is $\binom{n}{r}$.

If Bob is not a leader, how many ways are there to select the $r + 1$ leaders from the remaining $n$ people? This is $\binom{n}{r+1}$.

We have counted the ways to select $r + 1$ leaders in two different ways! Equating them:

Like before, we count one quantity in two ways.

How many ways are there to select $k + 1$ leaders among $n + 1$ people? This is $\binom{n+1}{k+1}$.

Now rank the $n + 1$ people by skill level, from 1 (best) to $n + 1$.

If the lowest-ranked leader has rank $k + 1$, how many ways are there to choose the other leaders? The other $k$ leaders must come from the $k$ people ranked above: $\binom{k}{k}$.

If the lowest-ranked leader has rank $k + 2$? There are $k + 1$ people ranked higher, so $\binom{k+1}{k}$.

We continue like this all the way to the end.

If the lowest-ranked leader has rank $n + 1$? There are $n$ people ranked higher, so $\binom{n}{k}$.

Casework on the lowest-ranked leader gives

ways to select the $k + 1$ leaders. We also found $\binom{n+1}{k+1}$ ways, so they must be equal!

What is the full stick from $\binom{k}{k}$ down to $\binom{n}{k}$? By the Hockey Stick Identity it is $\binom{n+1}{k+1}$.

What is the part you don't want, from $\binom{k}{k}$ down to $\binom{j-1}{k}$? The Hockey Stick Identity again: $\binom{j}{k+1}$.

Subtract. What's left is $\binom{j}{k} + \cdots + \binom{n}{k} = \binom{n+1}{k+1} - \binom{j}{k+1}$.