Suppose we are given several consecutive integer points at which a polynomial is evaluated. What information does this tell us about the polynomial? To answer this question, we create the following table, known as the Difference Table:
In the first column, we fill out the points at which the polynomial is evaluated (which I will assume is .
In the second column, we fill out the corresponding values of the polynomial at those points.
In the third column, we calculate the difference between two entries in the previous column. This is known as the first difference and is given by .
In the fourth column, we calculate the difference between two entries in the previous column. This is known as the second difference and is given by .
We continue building out subsequent columns of the table in this way, with .
For example, if we are given that is a quadratic polynomial satisfying
then the difference table is as follows:
Note that since we are not given , we are unable to calculate or . Now, there isn't (yet) any reason why this table would ever end; if we are given infinitely many values, we can always calculate the differences of terms. However, here is an interesting fact.
If a polynomial has degree , then the th difference is constant.
Furthermore, the th difference is equal to times the leading coefficient of .
In the above example, we see that . Since is a quadratic polynomial, the above fact tells us that for all , and this allows us to fill in other entries in the table. We get that so and hence ! These values are previously unknown to us, but the difference table allows us to calculate them without knowing the polynomial !
How do we prove this interesting fact? Let's consider a general polynomial of degree . We have
What is the value of ? By definition, we have
By the binomial theorem, we have
implying that there are no terms of degree in . Furthermore, the coefficient of comes solely from the term , and is equal to .
We may likewise continue by induction to consider the second difference, third difference, etc. Each time, we see that the degree of the polynomial decreases by 1. Hence, by the time we get to the th difference, it is a polynomial of degree 0. Since the only polynomials of degree 0 are the constants, this implies is a constant polynomial.
What happens to the leading coefficient at each step? We see that it gets multiplied by the degree of the (current) polynomial. Since the degree decreases by 1 at each step, we see that it gets multiplied by . Hence, we have , or that .
1. Construct the difference table for the function for to . Note that is a polynomial of degree .
Solution: This is a specially chosen function. We easily see that:
This allows us to easily calculate the first difference column as:
Similarly, for the th difference column, we have that
(*) Show that if is a polynomial of degree , then
In particular, the quadratic polynomial in the write up above satisfying and is given by .
2. Prove that there is no polynomial (of finite degree) which satisfies for all positive integers.
Solution: Construct the difference table for . Since , we see that is exactly equal to . This remains true for each th difference column, and hence there is no polynomial of degree that satisfies .