If you spent some time playing around with the procedure from Differences of powers of consecutive integers (namely, raise consecutive integers to the th power, and repeatedly take pairwise differences until reaching a single number) you probably noticed the curious fact that it always seems to result in a factorial—in the factorial of , to be precise.
Several commenters figured this out as well. Does this always happen? If so, can we prove it?
Let’s start by thinking about what happens when we do the successive-differencing procedure. If we start with the list , then we get . (I want to keep the letters in order, which is why I wrote instead of . Instead of subtracting the first value from the second, we can think of it as adding the negation of the first value to the second.) If we start with , we get
(The negation of is ; adding this to yields .) From we get
Do you see any patterns yet? Let’s do one more. From the above calculation we can already see that doing four iterations on will result in (do you see why?). Doing one final iteration gives us
Hmm. Let’s make a table.
I included one more row (which you can verify if you like). Now do you see a pattern? The coefficients seem to be taken from Pascal’s triangle, but with alternating signs!
In fact, it’s actually not too hard to see why this happens. At each step we take two offset copies of the previous row (by "offset" I mean that the letters are shifted by one, like and ) and add the negation of the first to the second. Since the signs are alternating, we really end up adding absolute values of the coefficients. Probably the best way to really see this is through an example:
Notice how we flip all the signs in the first row, so that they match the signs in the second row. But this is exactly how Pascal’s triangle is generated—each row is the sum of the previous row with itself, offset by one.
Now, in the real problem, we don’t start with , but with the th powers of consecutive integers. Let’s call the first integer , so the sequence of consecutive integers is . Given this, we can now write down an expression for what we end up with after doing the iterated difference procedure:
Let’s break this down a bit. We know that we get a sum of terms; that’s the part (you can read more about sigma notation here). We’ll use to index the terms. We also know that the terms alternate sign, so we need to include raised to some power involving ; the last term is always positive, so we use , which is equal to when . The binomial coefficient gives us the th entry on the th row of Pascal’s triangle. Finally, of course, is the th power of one of the integers we started with.
The claim, therefore, is that
And I will prove it to you, with pretty pictures, as promised!