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.