In my last post I reintroduced this seemingly odd phenomenon:
Start with consecutive integers and raise them all to the th power. Then repeatedly take pairwise differences (i.e. subtract the first from the second, and the second from the third, etc.) until you are left with only one number. That number will always be , that is factorial.
Simon Tatham left a comment on my previous post with a concise algebraic proof; perhaps I’ll write another post expanding on it. But for now I’m not interested in giving the shortest possible proof. My goal is to give a combinatorial proof, that is, a proof of the form “these two numbers must be equal because they are two different ways to count the same set of things”. Not because it is short or easy, but just because it is fun and involves some nice pictures!
So, where are we? In Differences of powers of consecutive integers, Part II, I showed that if we start out with the sequence of numbers and repeatedly take pairwise differences, we end up with a result that consists of adding and subtracting each a particular number of times. In particular, the number of times is added or subtracted is exactly the th entry on the th row of Pascal’s triangle, that is, . Also, they alternate being added or subtracted. Putting this together into formal notation, we end up with
See the above-linked post for an explanation of how Pascal’s triangle enters into it. In any case, our goal is to show this sum is actually equal to .
In Combinatorial proofs I explained the idea of a combinatorial proof in general, and gave a simple example involving binomial coefficients.
Then, in Making our equation count, I explained how different parts of this expression can be interpreted as counting something:
Factorial, , counts the number of permutations of things, or, from another point of view, the number of 1-1 matchings between two sets of things.
A binomial coefficient is the number of ways to choose exactly out of things.
Exponentiation, , counts the number of functions from a set of size to a set of size . For example, here are the different functions from a set of size 3 to another set of size 3.
Finally, that thing should look sort of familiar—any time you see an alternating sum like this, you should think of the Principle of Inclusion-Exclusion (PIE). More on this soon!