A combinatorial proof: the story so far

In my last post I reintroduced this seemingly odd phenomenon:

Start with $n+1$ consecutive integers and raise them all to the $n$ 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 $n!$ , that is $n$ 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 $k^n, (k+1)^n, \dots, (k+n)^n$ and repeatedly take pairwise differences, we end up with a result that consists of adding and subtracting each $(k+i)^n$ a particular number of times. In particular, the number of times $(k+i)^n$ is added or subtracted is exactly the $i$ th entry on the $n$ th row of Pascal’s triangle, that is, $\binom{n}{i}$ . Also, they alternate being added or subtracted. Putting this together into formal notation, we end up with

$\displaystyle \sum_{i=0}^n (-1)^{n-i} \binom{n}{i}(k+i)^n$

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 $n!$ .

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, $n!$ , counts the number of permutations of $n$ things, or, from another point of view, the number of 1-1 matchings between two sets of $n$ things.
A binomial coefficient $\binom{n}{i}$ is the number of ways to choose exactly $i$ out of $n$ things.
Exponentiation, $a^b$ , counts the number of functions from a set of size $b$ to a set of size $a$ . For example, here are the $3^3 = 27$ different functions from a set of size 3 to another set of size 3.
Finally, that $(-1)^{n-i}$ 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!