A combinatorial proof: reboot!

Posted on August 31, 2019 by Brent

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 $n + 1$ consecutive $n$ th powers, and repeatedly take pairwise differences, you always end up with $n!$ , that is, $n$ factorial.

Repeating the example I used in that post seven years ago, suppose we choose $n=4$ , and start with the five consecutive integers $23, 24, 25, 26, 27$ . We raise them all to the fourth power, giving us

$279841, 331776, 390625, 456976, 531441$

Now we take pairwise differences: $331776 - 279841 = 51935$ , then $390625 - 331776 = 58849$ , and so on, and we get the new list

$51935, 58849, 66351, 74465$

Repeating the difference procedure gives

$6914, 7502, 8114$

$588, 612$

$24$

And $24$ , of course, is $4! = 1 \cdot 2 \cdot 3 \cdot 4$ .

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

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

View all posts by Brent →

This entry was posted in arithmetic, combinatorics, proof and tagged consecutive, difference, integers, powers. Bookmark the permalink.

11 Responses to A combinatorial proof: reboot!

Simon Tatham says:

September 1, 2019 at 2:53 am

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 $(a_n)$ is given by a polynomial in $n$ whose leading coefficient is $n^k$ , then the first differences $(a_n-a_{n-1})$ are given by a polynomial whose leading coefficient is $kn^{k-1}$ (very like differentiation).

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

So, what are the $k$ th differences of the sequence $(n^k)$ itself? Iterating the lemma $k$ times tells us that they must be given by some polynomial whose leading coefficient is $(k\times(k-1)\times\cdots\times2\times1) n^0$ . The only such polynomial is the constant $k!$ .
- Brent says:
  
  September 2, 2019 at 11:40 am
  
  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…
  - Brent says:
    
    September 2, 2019 at 1:01 pm
    
    Hmm, maybe discrete calculus is something I should write about on this blog…
  - Simon Tatham says:
    
    September 9, 2019 at 7:02 am
    
    “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 $n$ th differences of a degree- $n$ poly are constant, then the $(n+1)$ th differences are *zero*, which means that if you have a sequence that you know is polynomial with degree at most $n$ , 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 $x_i = 4x_{i-1} - 6x_{i-2} + 4x_{i-3} - x_{i-4}$ .
    - Brent says:
      
      September 9, 2019 at 3:03 pm
      
      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.
      - Simon Tatham says:
        
        September 10, 2019 at 3:31 am
        
        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 $\leqslant n$ , 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- $n$ homogeneous linear difference equation, regardless of the coefficients of that equation.
        
        (But this time it has to be *exactly* order $n$ ; I don’t know of a formula that works without change if the sequence turns out to be of lower order.)
        
        Brent says:
        
        September 10, 2019 at 9:13 pm
        
        Interesting! Do you have this written up anywhere?
        
        Simon Tatham says:
        
        September 11, 2019 at 3:05 am
        
        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 $(a_n)$ satisfies a recurrence of the form $\sum_{i=0}^d c_i a_{n+i} = 0$ , then consider the $d\times d$ matrix whose $(ij)$ th element is $a_{n+i+j}$ . 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 $(c_i)$ , 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 $a_{n+2d}$ in terms of the previous elements! For example, with $d=2$ , you take the determinant of $\begin{pmatrix} a&b&c \\ b&c&d \\ c&d&e\\ \end{pmatrix}$ , set it equal to 0, and solve for $e$ , to get $e=\frac{ad^2-2bcd+c^3}{ac-b^2}$ . 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 $a_n = n 2^n$ , 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 $a_{n+2d}$ 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.
        
        Simon Tatham says:
        
        September 11, 2019 at 3:05 am
        
        (Sigh, there’s always one. The $(d+1)\times(d+1)$ matrix, not $d\times d$ .)
        
        Brent says:
        
        September 11, 2019 at 5:18 pm
        
        I see, very cool!
Pingback: A combinatorial proof: the story so far | The Math Less Traveled