# Writing a Combinatorial Proof

This started life as a post on Quora, answering the question:

For any positive integer $n$, how do you write a combinatorial proof of the identity

$\displaystyle {2n \choose n} = \sum_{i = 0}^{n} {n \choose i} {n \choose n-i}$?

To write a combinatorial proof, the idea is to describe how each side of the equation is actually counting the same set of objects.

Now, if you have a set of $2n$ objects, $\displaystyle {2n \choose n}$ (that is $2n$ choose $n$) is the number of subsets of that set which contain exactly $n$ of them.

Now pretend that you’ve taken your $2n$ objects and put them into two boxes with $n$ objects in each. Think about what each of your terms on the other side of the equation, $\displaystyle {n \choose i}{n \choose n-i}$ represent. Then consider what you get when you add all of these together. You should be able to explain that this really does count the same thing as $\displaystyle {2n \choose n}$.

Now when I wrote the above, I wondered if this was a homework question someone had posted to Quora.  I didn’t fill in all the details since, while I’m happy to help someone with their homework, I don’t want to do it for them.

But in case anyone wants to see a worked out example, here’s the standard initial example of a combinatorial proof.  This is the identity that makes Pascal’s Triangle work as nicely as it does.

Theorem: $\displaystyle {n \choose k} = {n-1 \choose k} + {n-1 \choose k-1}$.

Proof: Let’s start by thinking about the expression on the left.  If we have a set with $n$ objects in it, $\displaystyle {n \choose k}$ is the number of ways we can select a subset of $k$ objects.  To say that another way, it’s the number of ways we can pick $k$ objects out of our set without caring what order they’re in.

Now suppose one of our objects has decided to wear a hat.  If we’re looking to select a subset with $k$ objects, we can decide to include or exclude the one wearing the hat.

Say we don’t want to include the guy with the hat.  In that case, all $k$ objects, have to be selected from the $n-1$ objects that aren’t wearing hats.  We can do this in $\displaystyle {n-1 \choose k}$ different ways.

Now suppose we decide to include the one with the hat.  Well then, to get $k$ objects altogether, we need to select $k-1$ more from the set.  There’s $\displaystyle {n-1 \choose k-1}$ ways to get the rest of the objects that you need.

Putting these two together we see that $\displaystyle {n-1 \choose k} + {n-1 \choose k-1}$ is also the number of ways to select a subset of $k$ objects from a set containing $n$ things.

Therefore, our identity must be true.

If you’d like to try one on your own, $\displaystyle 2^n = \sum_{i = 0}^{n} {n \choose i}$ is another nice example.