Differences of powers of consecutive integers, part II

If you spent some time playing around with the procedure from Differences of powers of consecutive integers (namely, raise $n+1$ consecutive integers to the $n$ 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 $n$ , to be precise.

For example:

$3^2, 4^2, 5^2 = 9,16,25 \to 7,9 \to 2$

$196^2, 197^2, 198^2 = 38416,38809,39204 \to 393,395 \to 2$

$7^3, 8^3, 9^3, 10^3 = 343,512,729,1000 \to 169,217,271 \to 48,54 \to 6$

$0^4,1^4,2^4,3^4,4^4 = 0,1,16,81,256 \to 1,15,65,175 \to 14,50,110 \to 36,60 \to 24$

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 $a,b$ , then we get $-a + b$ . (I want to keep the letters in order, which is why I wrote $-a + b$ instead of $b - a$ . 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 $a,b,c$ , we get

$a,b,c \to (-a+b), (-b+c) \to (a - 2b + c)$ .

(The negation of $(-a + b)$ is $(a - b)$ ; adding this to $(-b + c)$ yields $(a - 2b + c)$ .) From $a,b,c,d$ we get

$a,b,c,d \to \\ (-a+b), (-b+c), (-c+d) \to \\ (a - 2b + c), (b - 2c + d) \to \\ (-a + 3b - 3c + d).$

Do you see any patterns yet? Let’s do one more. From the above calculation we can already see that doing four iterations on $a,b,c,d,e$ will result in $(-a + 3b - 3c + d), (-b + 3c - 3d + e)$ (do you see why?). Doing one final iteration gives us

$a - 4b + 6c - 4d + e$ .

Hmm. Let’s make a table.

$n$	Result
1	$-a + b$
2	$a - 2b + c$
3	$-a + 3b - 3c + d$
4	$a - 4b + 6c - 4d + e$
5	$-a + 5b - 10c + 10d - 5e + f$

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 $(a - 2b + c)$ and $(b - 2c + d)$ ) 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:

$\begin{array}{cccccccccc} -( & -a & + & 3b & - & 3c & + & d & ) & \\ & & & -b & + & 3c & - & 3d & + & e \\ \hline & a & - & 4b & + & 6c & - & 4d & + & e \end{array}$

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 $a,b,c,d,\dots$ , but with the $n$ th powers of $n+1$ consecutive integers. Let’s call the first integer $k$ , so the sequence of consecutive integers is $k, k+1, k+2, \dots, k+n$ . Given this, we can now write down an expression for what we end up with after doing the iterated difference procedure:

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

Let’s break this down a bit. We know that we get a sum of $n+1$ terms; that’s the $\sum_{i=0}^n$ part (you can read more about sigma notation here). We’ll use $i$ to index the terms. We also know that the terms alternate sign, so we need to include $(-1)$ raised to some power involving $i$ ; the last term is always positive, so we use $(-1)^{n-i}$ , which is equal to $1$ when $i = n$ . The binomial coefficient $\binom n i$ gives us the $i$ th entry on the $n$ th row of Pascal’s triangle. Finally, of course, $(k+i)^n$ is the $n$ th power of one of the integers we started with.