If I am given the values of a polynomial at some consecutive integers and I want to find its value at the next integer, how might I proceed? For example, if I know how would I find ?

The easiest way I know is to set up a finite difference table. Write the polynomial values in a row, then underneath each row write the difference of the two numbers above it. Continue until all the numbers in a row are equal (or the row below it contains 0s).

For example:

Then we extrapolate by starting at the bottom row and writing the next equal number (in this case 6), then proceeding upwards by writing the sum of the number to its left and below it. In our example we obtain the following.

Hence we conclude that . Notice that we did not need to find for general (it turns out to be in this example).

The above principle works based on the fact that if is a polynomial, then reduces its degree by . By doing this successively the degree eventually becomes 0. Constant polynomials are uniquely determined by one value so by extrapolating this and propagating the result upwards, we can extrapolate any degree of polynomial in a unique manner provided we have a complete table.

What if we wanted to find in the above example? Would we have to resort to finding by solving a system of linear equations in its coefficients? That is, do we need to set , substitute known values and then solve for ? In this post I want to show how to proceed in a different way.

Firstly, consider what occurs if our original row were taken from a diagonal of Pascal’s triangle (i.e. binomial coefficients). For example, here in the first row we show numbers of the form .

We find the second row has numbers of the form and the third row has numbers of the form . In general if the first row has numbers of the form (where is fixed and varies), then the ‘th row has numbers of the form . This is a consequence of the fundamental identity

Given this, it makes sense to try to write our polynomial as a linear combination of binomial coefficients () rather than as a linear combination of monomials ().

Returning to our previous example, we wish to evaluate given . Notice how the entire finite difference table can be generated from its first diagonal (running NW-SE). For example,

This shows that can be written in terms of the first diagonal with the binomial coefficients . Another way of thinking of this is to see how many ways each number in the first diagonal can trickle across the table. In the above example, the number can trickle up to in ways: it needs to go up twice and across once in three total moves (up-up-across, up-across-up or across-up-up). This should hopefully explain how the binomial coefficients enter the picture. In general if we need to go across places and up places, this can be done in ways.

Now if we wish to find , we need to go spaces across from , nine spaces across and one space up from , eight spaces across and two spaces up from , and seven spaces across and three spaces up from . We conclude that we may write

Hence . In general, if the first diagonal of the table is and , then

There is actually a strong link here between this formula and the Taylor series expansion, forming the basis for umbral calculus. See [2] for more details.

#### References

[1] Jim Loy’s pages, Finite Difference

[2] Weisstein, Eric W. “Newton’s Forward Difference Formula.” From *MathWorld*–A Wolfram Web Resource. http://mathworld.wolfram.com/NewtonsForwardDifferenceFormula.html

[…] out of thin air!) is to write down a finite difference table – refer to an earlier blog post here: if the first diagonal of the table is where , […]

Pingback by Polynomial extrapolation of finite exponential sequences | Chaitanya's Random Pages — September 16, 2013 @ 11:41 am |