Continuing from a previous post, we found that if we begin with th powers of consecutive integers and then repeatedly take successive differences, it seems like we always end up with the factorial of , that is, . We then derived an algebraic expression for the result of the iterative difference procedure. So the goal now is to prove that
Now, it’s possible (probable, in fact) that this can be proved by purely algebraic means. If you come up with such a proof I would love to see it! But I must confess that I spent several hours banging my head against it (algebraically speaking) without making any progress. Eventually I turned to the idea of a combinatorial proof.
What do I mean by that? Combinatorics is the subfield of mathematics concerned with counting. The essence of a combinatorial proof is to show that two different expressions are just two different ways of counting the same set of objects—and must therefore be equal. I’ve described some combinatorial proofs before, in counting the number of ways to distribute cookies.
As another simple example, consider the binomial coefficient identity
It’s certainly possible to prove this algebraically, by expanding out the binomial coefficients (using ), but we can give a more elegant proof, based on the fact that is the number of ways to choose a subset of things out of a set of things. For example, here are the ways to choose three things out a set of five:
Consider the first element of the size- set. Every subset of size either includes this first element, or it doesn’t. The number of size- subsets which do not include the first element is , since that’s the number of ways to choose things from the remaining elements. The number of size- subsets which do include the first element is , because they correspond to choosing of the remaining things. Therefore .
Here’s an illustration of how this works in the particular case when and :
Notice how the ten subsets from above have been split into two groups: the first group, on the left, are those that don’t include the first element; you can see that each of them corresponds to one of the size- subsets of the remaining four elements. The second group, on the right, are those that do include the first element; each corresponds to one of the size- subsets of the remaining four elements.
So that’s the idea of a combinatorial proof. And we want to do something similar for the identity we are trying to prove—although, of course, it’s going to be a bit more difficult!
You might have fun trying to think about what a combinatorial proof of our target equation might look like; although if you don’t have much experience with combinatorics you may have trouble coming up with what sorts of things the two sides of the equation might be counting! That’s what I’ll talk about in my next post.