## Follow Up: Differences

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 . . . . .04 32 108 256 500 . . . . .428 76 148 244 . . . . .2448 72 96 . . . . .2424 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) = n^{4} – 2 n^{3} + n^{2} – 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 a_{k} (on the top row), on down to a_{0} on the bottom row.

a_{k} . . . .

a_{k-1} . . . . .

. . . . .

a_{1} . . . . .

a_{0}. . . . .

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

P_{i}(j) = a_{0} C(j,i-0) + a_{1} C(j,i-1) + . . . + a_{i} 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 a_{0} C(j,0) = a_{0}, so check! Also, on the left of each row, the entry, sure enough is P_{i}(0) = a_{i} + a_{1} 0 + . . . + a_{i} 0 = a_{i}

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 P_{i}(j-1) and for (b), the entry is P_{i-1}(j-1)

All we have to show is that the value we hope is there, namely P_{i}(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!

P_{i}(j-1) + P_{i-1}(j-1) =

a_{0} C(j-1,i-0) + a_{1} C(j-1,i-1) + . . . + a_{i-1} C(j-1,1) + a_{i} C(j-1,0) +

a_{0} C(j-1,i-1) + a_{1} C(j-1,i-2) + . . . + a_{i-1} C(j-1,0)

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

a_{0} C(j,i-0) + a_{1} C(j,i-1) + . . . + a_{i-1} C(j,1) + a_{i} 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 P_{i}(j) as promised.

## 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.

## strauss said,

February 3, 2009 at 7:55 am

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