Category: Proof Writing

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.

How do you prove a conjecture is false?

First posted to Quora on Friday, 7 September 2018

That depends on the nature of the statement.

If you have a universal statement, which is to say a statement that all of the things in some category share some property, you merely have to provide a counter-example.

So if you wanted to disprove the statement, “all prime numbers are odd” you’d merely have to point out that 2 is even and the statement cannot be true.

Disproving an existential statement is usually more work. These statements say that there is at least one thing that has a particular property. To disprove an existential statement, you need a general argument that that property can never happen.

So to prove that the statement “There is a pair of even integers whose sum is odd” is false, you must prove that the sum of any two even integers must be even.

Those are the cases “all” and “some.” The cases “none” and “some are not” are similar.

To disprove a statement like “None of the items in set A have property B” you simply have to find one that does. If you want to show a statement like “Some of the items in set A do not have property B” is false you need a general argument that everything in A has property B.

In any case, disproving a statement is equivalent to proving its negation.