This started life as a post on Quora, answering the question:
For any positive integer , how do you write a combinatorial proof of the identity
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 objects, (that is choose ) is the number of subsets of that set which contain exactly of them.
Now pretend that you’ve taken your objects and put them into two boxes with objects in each. Think about what each of your terms on the other side of the equation, 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 .
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.
Proof: Let’s start by thinking about the expression on the left. If we have a set with objects in it, is the number of ways we can select a subset of objects. To say that another way, it’s the number of ways we can pick 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 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 objects, have to be selected from the objects that aren’t wearing hats. We can do this in different ways.
Now suppose we decide to include the one with the hat. Well then, to get objects altogether, we need to select more from the set. There’s ways to get the rest of the objects that you need.
Putting these two together we see that is also the number of ways to select a subset of objects from a set containing things.
Therefore, our identity must be true.
If you’d like to try one on your own, is another nice example.