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) = n⁴ – 2 n³ + n² – 1

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

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₀ on the bottom row.

a_k . . . .

 a_k-1 . . . . .

    . . . . .

     a₁ . . . . .

      a₀. . . . .

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₀ C(j,i-0) + a₁ 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₀ C(j,0) = a₀, so check! Also, on the left of each row, the entry, sure enough is P_i(0) = a_i + a₁ 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₀ C(j-1,i-0) + a₁ C(j-1,i-1) + . . .  + a_i-1 C(j-1,1) + a_i C(j-1,0) +

a₀ C(j-1,i-1) + a₁ 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₀ C(j,i-0) + a₁ 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.