More than seven years ago I wrote about a curious phenomenon, which I found out about from Patrick Vennebush: if you start with a sequence of consecutive th powers, and repeatedly take pairwise differences, you always end up with , that is, factorial.

Repeating the example I used in that post seven years ago, suppose we choose , and start with the five consecutive integers . We raise them all to the fourth power, giving us

Now we take pairwise differences: , then , and so on, and we get the new list

Repeating the difference procedure gives

And , of course, is .

I came up with a very cool proof of this, and started to explain it, but got stuck on how to explain the Principle of Inclusion-Exclusion (PIE). But now that I’ve finally done that in the last six posts (A probability puzzle, Probabilistic PIE, Have a piece of PIE, Formal PIE, PIE: proof by algebra, PIE: proof by counting), I’m finally going to finish it! Next time I’ll recap the story so far, with links back to my previous posts, and then we’ll forge onward.

##
About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

Not to spoil your fun – I certainly wouldn’t deny the value of proving things by a roundabout route so as to learn other useful things on the way, and PIE is very useful in its own right – but this result has a pretty short proof.

Lemma: if a sequence is given by a polynomial in $n$ whose leading coefficient is , then the first differences are given by a polynomial whose leading coefficient is (very like differentiation).

Proof: induction on . It’s certainly true of the polynomial itself, just by expanding out . Adding on terms of degree doesn't change the result, because by the inductive hypothesis, all those terms contribute terms of degree to the first differences, i.e. don't affect the leading term. And the base case is that if , the sequence consists of consecutive integers, so its first differences are all 1.

So, what are the th differences of the sequence itself? Iterating the lemma times tells us that they must be given by some polynomial whose leading coefficient is . The only such polynomial is the constant .

Ah, thanks for pointing this out, this makes perfect sense. Indeed, taking successive differences *is* exactly a discrete analogue to differentiation (see e.g. Concrete Mathematics by Graham, Knuth, & Patashnik). I like how your proof also shows that a sequence of nth powers is not special — a sequence of values which are consecutive outputs from any nth-degree polynomial (with a leading coefficient of 1) will yield the same result.

In any case, don’t worry, you definitely haven’t spoiled my fun. =) I just thought it would be cool to see if we could give this result a combinatorial interpretation, and indeed we can. Now I am inspired to see whether we can give a suitable combinatorial interpretation to the result generalized to any polynomial as well…

Hmm, maybe discrete calculus is something I should write about on this blog…

“a sequence of nth powers is not special”: indeed, the reason this result and its proof were so firmly stuck in my head was that when I was a teenager I used to use this very technique for solving ‘find the { next number in | generating formula for } this sequence’ puzzles. If you have reason to believe your sequence is polynomial, then take differences until you get a constant, and then you know its degree *and* its leading term, so you can subtract that off to get a reduced sequence and repeat.

(Not the only way, of course: once you know the degree, you could instead use something like Lagrange’s formula to do the rest of the job in one go. But this was the technique I knew first.)

Perhaps an even nicer corollary is that if the th differences of a degree- poly are constant, then the th differences are *zero*, which means that if you have a sequence that you know is polynomial with degree at most , then you can use a fixed recurrence relation to generate further terms in the sequence without even *bothering* to identify the polynomial itself. For example, any cubic (or simpler) polynomial sequence satisfies the recurrence .

Ah, very nice! As you may be aware, Charles Babbage’s Difference Engine worked by essentially the same method. I have never before seen the result about fixed recurrence relations, but now that you write it down it makes perfect sense. I think of it in terms of writing out the sequence, writing successive differences below it, then successive differences of that below again, and so on until reaching all zeros, then working backwards using addition to extend the table further and thus extend the sequence. (This is how the Difference Engine worked.) This ends up doing the same thing as your fixed recurrence relations because as you add back up, the number of copies of each term that contributes to a term on the top row is determined by an entry of Pascal’s triangle—in particular, it’s the number of paths that exist from a particular term somewhere in the table to a particular term in the top row, if you can only move up&left or up&right.

I actually have a second example of a “universal continuation formula”, by which I mean, something that can generate further terms in any of a large family of sequences without having to identify the specific formula that generated this sequence.

The one we’ve just been discussing works for any polynomial sequence of degree , without having to identify the coefficients of the polynomial. It’s also possible to find a universal continuation formula that works for any sequence which satisfies an order- homogeneous linear difference equation, regardless of the coefficients of that equation.

(But this time it has to be *exactly* order ; I don’t know of a formula that works without change if the sequence turns out to be of lower order.)

Interesting! Do you have this written up anywhere?

Nowhere public, I’m afraid; it’s one of a big junkpile of jottings that I’ve never really got round to polishing up to put on my website.

The technique is matrix-based. If a sequence satisfies a recurrence of the form , then consider the matrix whose th element is . Each row of that matrix satisfies that recurrence, i.e. if the elements in the row are combined in the linear combination given by the , you get zero. But that means the columns of the matrices themselves also give the zero vector when summed in that same linear combination. In other words, the matrix is singular.

So, write down the determinant of the matrix, set it equal to zero, and rearrange that equation so that it gives the highest-index element in terms of the previous elements! For example, with , you take the determinant of , set it equal to 0, and solve for , to get . And you can check for yourself that this will correctly extend any sequence generated by an order-2 homogeneous linear difference equation: the Fibonacci numbers, the sequence , the ordinary integers, a sequence in which every number is 10 times the previous one minus twice the one before that, you name it. You just have to give it four consecutive terms (which is just enough, of course, to give the coefficients of the recurrence and the necessary number of starting terms), and it’ll deliver you the next one.

But it doesn’t work for lower-degree sequences, because the coefficient of in the determinant – i.e. the denominator of the rearranged expression – is always going to be the determinant of the submatrix formed by removing the last row and column. So if the sequence satisfies any lower-degree recurrence, then that submatrix will also be singular, and the continuation formula will attempt to divide by zero.

(Sigh, there’s always one. The matrix, not .)

I see, very cool!

Pingback: A combinatorial proof: the story so far | The Math Less Traveled