Given a difference table, as we considered back in EV. What’s the Difference , how do we come up with a polynomial that gives the values on the top row?

For example, suppose we have

```-1     -1     3     35     143     399     899 . . . . .
0     4     32    108     256     500  . . . . .
4    28    76     148      244  . . . . .
24    48     72       96   . . . . .
24     24    24    . . . . .```

What is the polynomial P(n), of degree four, that gives

P(0) = -1 P(1) = -1 P(2) = 3 P(3) = 35 P(4) = 143 , etc.

Can this be expressed simply in terms of the leading values on the left of the table: -1, 0, 4, 24, 24?

And finally, what is the general rule?

Wonderfully, beautifully, the answer is, just as tricycle and prunthaban said in the comments:

24 C(n,4) + 24 C(n,3) + 4 C(n,2) + 0 C(n,1) + (-1) C(n,0)

Where C(n,j) = (n)(n-1)(n-2) … (total of j terms) / j!

For example, C(n,4) = n (n-1) (n-2) (n-3) / 4! In the special case when j=0, we set C(n,0)=1.

So our polynomial here is

(24/4!) (n) (n-1) (n-2) (n-3) + (24/3!) (n) (n-1) (n-2) + (4/2!) (n) (n-1) + (0/1!) (n) + (-1)

That isn’t very “simplified”, but at least we can see the pattern! If we multiply the whole thing out, we get

P(n) = n4 – 2 n3 + n2 – 1

but it’s hard to see the connection, in this ‘simplified’ form, to the original data.

Before proving that this is correct in general, let’s take a moment to discuss some of the properties of C(n,j), often read “n choose j”. When n is actually a counting number, this really is the number of ways to choose j out of n objects; but we’ve defined things more generally here: n could be a real number, or simply a variable (as in our expression for P).

A key property is that C(n,m) + C(n,m+1) = C(n+1,m+1).

This is just a matter of algebra:

C(n,m) + C(n,m+1) = (n) … (n-m+1) / m! + (n) … (n-m+1)(n-m)/ (m+1)!

= you do this part

= (n+1) (n) … (n-m+1) / (m+1)! = C(n+1, m+1).

This is precisely why, these are the numbers that fill in Pascal’s triangle: C(n, m) is the mth entry on the nth row.

Now, how hard is our assertion, that our polynomial is the correct one? Not very, really. Suppose we have a difference table with entries on the left ak (on the top row), on down to a0 on the bottom row.

ak . . . .

ak-1 . . . . .

. . . . .

a1 . . . . .

a0. . . . .

Then we claim that the jth entry (counting from 0) entries on the ith row (counting up from the bottom 0th row) are given by

Pi(j) = a0 C(j,i-0) + a1 C(j,i-1) + . . .  + ai C(j,i-i)

To prove this, we first show it’s true for the bottom row, then the next row up, etc, etc, clicking along like a typewriter from left to right. (This is just induction on i and j)

For the bottom row, things are pretty easy: all the entries are a0 C(j,0) = a0, so check! Also, on the left of each row, the entry, sure enough is Pi(0) = ai + a1 0 + . . .  + ai 0 = ai

since (C(0,i) = 0, unless i=0 also– try it!)

Suppose we’ve walked all the way up the spot we care about, on the ith row, jth position. When we get there we will have proven our formula is correct for all the entries below, and for all the entries to the left.

In particular, when we reach the ith row, jth position, we know that (a) the formula is correct for the entry to the left, and (b) the formula is correct for the entry on the row below, to the left. For (a), the entry is Pi(j-1) and for (b), the entry is Pi-1(j-1)

All we have to show is that the value we hope is there, namely Pi(j), is what we get when we add (a) to (b), i.e. would be the correct entry in the difference table. So lets try it!

Pi(j-1) + Pi-1(j-1) =

a0 C(j-1,i-0) + a1 C(j-1,i-1) + . . .  + ai-1 C(j-1,1) + ai C(j-1,0) +

a0 C(j-1,i-1) + a1 C(j-1,i-2) + . . .  + ai-1 C(j-1,0)

Gathering our a’s and using our identity, it falls into place, and we get the desired sum:

a0 C(j,i-0) + a1 C(j,i-1) + . . .  + ai-1 C(j,1) + ai C(j-1,0)

What about this last term? C(j-1,0) = 1, as does C(j,0), so we are set. Our total is Pi(j) as promised.

1. physicsfreak said,

January 21, 2009 at 4:27 pm

Hi, I realize this may be somewhat of an idiotic question, but I cannot for the life of me see /why/ we are using combinations here — I realize that the method works, but I don’t know how to make it… intuitive. And what of newton coming up with this? where is it published?

— Thanks so much for any help.

2. strauss said,

February 3, 2009 at 7:55 am

The simplest (quite unsatisfying) answer is just as you say: that it works!

Let’s see: how to make it intuitive? I am not sure I have a satisfying answer, except to note that the simplest example of this phenomenon is Pascal’s triangle itself: sketch out what happens if the entries on the left of all but the bottom row are 0’s and the entry on the left of the bottom row is 1. Actually draw this out! After a time, a slice of Pascal’s triangle will appear, turned on its side. The entries along the top row will be C(n,k) (where there are k rows); we can think of this as a polynomial in n, or as a combination in n, either way.
The more general case is just a linear combination of multiples of this example, for different k’s.
Don’t know that that is much more satisfying, though!
A really terrific reference on closely related topics (particularly, Stirling numbers) is in the beginning of Chapter 1, Vol 1 of Donald Knuth’s The Art of Computer Programming; don’t overlook the exercises!
The reference that tipped us off to this, but says less than we have said here, is Martin Gardner’s Colossal Book of Mathematics.