Method of Differences

The method of finite differences gives us a way to calculate a polynomial using its values at several consecutive points. This is often a good approach to finding the general term in a pattern, if we suspect that it follows a polynomial form.

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:

\[ \begin{array} {l l l l l l l} n & f(n) & D_1(n) & D_2(n) & D_3(n) & \ldots \\ 1 & \\ 2 & \\ 3 & \\ \vdots \\ \end{array} \]

• In the first column, we fill out the points at which the polynomial is evaluated (which I will assume is \(1, 2, 3\ldots\)).
• 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 \( D_1 (n) = f(n+1) - f(n) \).
• 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 \( D_2 (n) = D_1 (n+1) - D_1 (n) \).

We continue building out subsequent columns of the table in this way, with \( D_{k+1} (n) = D_k (n+1) - D_k (n) \).

For example, if we are given that \( f(n) \) is a quadratic polynomial satisfying

\[\begin{array} &f(1) = 4, &f(2) = 3, &f(3) = 4, &f(4) = 7, &f(5) = 12, \end{array}\]

then the difference table is as follows:

\[ \begin{array} {lrrrr} n & f(n) & D_1(n) & D_2(n) & D_3(n) & \ldots \\ 1 & 4 & -1 & 2 & 0 \\ 2 & 3 & 1 & 2 & 0\\ 3 & 4 & 3 & 2\\ 4 & 7 & 5 \\ 5 & 12 & \\ \vdots \\ \end{array} \]

Note that since we are not given \(f(6) \), we are unable to calculate \(D_1(5), D_2(4), D_3(3)\) or \(D_4(2)\). 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 \(f(x) \) has degree \(k\), then the \(k^\text{th}\) difference is constant.
Furthermore, the \(k^\text{th}\) difference is equal to \(k!\) times the leading coefficient of \(f(x). \ _\square\)

See proof below.

In the above example, we see that \( D_2 (1) = D_2(2) = D_2( 3) = 2 \). Since \(f(x)\) is a quadratic polynomial, the above fact tells us that \( D_2(n) = 2 \) for all \(n\), and this allows us to fill in other entries in the table. We get that \( D_2(4) = 2 \) so \( D_1 (5) = 7 \) and hence \(f(6) = 19 \). These values are previously unknown to us, but the difference table allows us to calculate them without knowing the polynomial \(f(x)\)!

We can continue the difference table as follows:

\[ \begin{array} {lrrrr} n & f(n) & D_1(n) & D_2(n) & D_3(n) & \ldots \\ 1 & 4 & -1 & 2 & 0 \\ 2 & 3 & 1 & 2 & 0\\ 3 & 4 & 3 & 2 & 0\\ 4 & 7 & 5 & 2 & 0\\ 5 & 12 & 7 & 2 & 0\\ 6 & 19 & 9 & 2 & 0\\ \vdots \\ \end{array} \]

If \( f(x) \) is a quadratic polynomial that satisfies \( f(1) = 3, f(2) = 9, f(3) = 19 \), what is \( f(4)? \)

---

We construct the difference table using the initial data, and obtain

\[ \begin{array} {lrrr} n & f(n) & D_1(n) & D_2(n) \\ 1 & 3 & 6 & 4 \\ 2 & 9 & 10& \\ 3 & 19 & & \\ 4 & & & \\ \end{array} \]

From the above theorem, we know that \( D_2(n) \) is a constant, and thus is equal to 4. This allows us to complete the table as follows:

\[ \begin{array} {lrrr} n & f(n) & D_1(n) & D_2(n) \\ 1 & 3 & 6 & 4 \\ 2 & 9 & 10 & 4 \\ 3 & 19 & 14 & 4 \\ 4 & 33 & 18 & 4 \\ \end{array} \]

Hence, \(f(4) = 33 \). \(_\square\)

If \( g(x) \) is a cubic polynomial that satisfies \[\begin{array} &g(0) = 0, &g(1) = 3, &g(2) = 2, &g(3) = 1, \end{array}\] what is \( g(5) ?\)

---

We construct the difference table, using the initial data. Note that it doesn't matter what number we start with, as long as the difference is 1.

\[ \begin{array} {lrrrr} n & g(n) & D_1(n) & D_2(n) & D_3 (n) \\ 0 & 0 & 3 & -4 & 4 \\ 1 & 3 & -1 & 0 \\ 2 & 2 & -1& \\ 3 & 1 & & \\ \end{array} \]

From the above, we know that \( D_3(n) \) is a constant, and thus it is equal to 4. This allows us to complete the table as follows. Note that we want to calculate \( g(5) \) and thus need to extend the table by more rows.

\[ \begin{array} {lrrrr} n & g(n) & D_1(n) & D_2(n) & D_3 (n) \\ 0 & 0 & 3 & -4 & 4 \\ 1 & 3 & -1 & 0 & 4 \\ 2 & 2 & -1 & 4 & 4 \\ 3 & 1 & 3 & 8 & 4 \\ 4 & 4 & 11 & 12 & 4 \\ 5 & 15 & 23 & 16 & 4 \\ \end{array} \]

Hence, \( g(5) = 15 \). \(_\square\)

Construct the difference table for the function \( f_k(n) = (n-1) \times (n-2) \times \cdots \times (n-k) \) for \( n =1 \) to \( k+1 \). Note that \(f_k(n) \) is a polynomial of degree \(k\).

---

This is a specially chosen function. We easily see that

\[ f(i) = \begin{cases} 0 & i = 1 \mbox{ to } k \\ k! & i = k+1. \\ \end{cases}\]

This allows us to easily calculate the first difference column as

\[ D_1(i) = \begin{cases} 0 & i = 1 \mbox{ to } k-1 \\ k! & i = k . \end{cases} \]

Similarly, for the \(j^\text{th}\) difference column, we have

\[ D_j (i) = \begin{cases} 0 & i = 1 \mbox{ to } k-j \\ k! & i = k-j+1. \end{cases}\]

To summarize the above, the difference table is

\[ \begin{array} {rrrrrrrr} n & f_k(n) & D_ 1 (n) & D_2(n) & \ldots & D_{k-1} (n) & D_{k} (n) \\ 1 & 0 & 0 & 0 & \ldots & 0 & k!\\ 2 & 0 & 0 & 0 & \ldots & k! \\ 3 & 0 & 0 & 0 & \ldots & \\ \vdots \\ k & 0 & k! \\ k+1 & k! & &&&&& _\square \\ \end{array} \]

If a polynomial \(f(x)\) has degree \(k\), then the \(k^\text{th}\) difference is constant.
Furthermore, the \(k^\text{th}\) difference is equal to \(k!\) times the leading coefficient of \(f(x). \ _\square\)

Let's consider a general polynomial of degree \(k\). We have

\[ f(n) = a_k n^k + a_{k-1} n^{k-1} + \ldots + a_1 n + a_0. \]

What is the value of \( D_1(n) \)? By definition, we have

\[ D_1(n) = f(n+1) - f(n) = \sum_{i=1}^k a_i \left[(n+1)^i - n^i\right] .\]

By the binomial theorem, we have

\[ (n+1)^{i} - n^i = {i \choose 1} n^{i-1} + {i \choose 2} n^{i-2} + \cdots + {i \choose i - 1} n^1 + {i \choose i } n^0, \]

implying that there are no terms of degree \(n^k\) in \(D_1(n) \). Furthermore, the coefficient of \( n^{k-1} \) comes solely from the term \(a_k \left[(n+1)^k - n^k\right] \), and is equal to \( k a_k \).

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 \(k^\text{th}\) difference, it is a polynomial of degree 0. Since the only polynomials of degree 0 are the constants, this implies \(D_k(n) \) 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 \( k \times (k-1) \times \cdots \times 2 \times 1 = k! \). Hence, we have \( D_k = a_k \times k! \) or \( a_k = \frac{D_k} { k!} \). \(_\square\)

If we have an entire row of the difference table, we can reconstruct the polynomial using the following theorem:

Let \( f_k(n) = (n-1) \times (n-2) \times \cdots \times (n-k) \) as defined above.

If \(f(n) \) is a polynomial of degree \(k\), then \[ f(n) = f(1) + \sum_{i=1}^k \frac{D_i (1)}{i!} \times f_i (n). \ _\square\]

In particular, the quadratic polynomial \(f\) in the first example satisfying \( f(1) = 3, f(2) = 9, f(3) = 19 \) is given by \[ \begin{array}{l l} f(n) & = 3 + \frac{6}{1!} (n-1) + \frac{ 4}{2!} (n-1)(n-2) \\ & = 2n^2 + 1. \end{array} \] The cubic polynomial \(g\) in the second example satisfying \( g(0) = 0, g(1) = 3, g(2) = 2, g(3) = 1 \) is given by \[ \begin{array} { l l } g(n) & = 3 + \frac{ -1}{1!} (n-1) + \frac{ 0}{2!} (n-1)(n-2) + \frac{ 4}{ 3!} (n-1)(n-2)(n-3) \\ & = \frac{1}{3} ( 2n^3 - 12n^2 + 19 n ). \end{array} \]

As worked out in the above example, this theorem is true for the special case of the polynomial \( f_k (n) \). Observe that for any 2 polynomials \(g(n) \) and \( h(n) \), we clearly have \( D_i (g+h) (n) = D_i g(n) + D_i h(n) \), and \( D_i ( \alpha g) (n) = \alpha D_i g (n) \). Hence, the theorem is true for any polynomial that can be written as a linear combination of \( f_k (n) \).

Now, given any polynomial \(f(n) \) of degree \(k\), we will show that there are unique coefficients \( \{ \alpha_i \} _{i=1}^{k} \) such that

\[ f(n) = f(1) + \sum_{i=1}^k \alpha_i f_i (n). \]

These coefficients can be obtained by setting \( n = 2\) to find \( \alpha_1 \), and then setting \( n = 3 \) to find \( \alpha_2 \), so on and so forth. We get an identity, because both sides are polynomials of degree at most \(k\), which agree on \( k + 1 \) values.

Hence, this theorem is true for all polynomials \(f(n) \). \(_\square\)

Find a quadratic polynomial which satisfies \( f(1) = 3, f(3) = 6, f(5 ) = 10 \).

---

Notice that we are given the values at 1, 3, 5, and hence cannot apply the method of finite differences directly. Instead, we will define a new polynomial given by \( f( 2x - 1) = g ( x) \). With this, we get that \( g(1) = f(1) = 3, g(2) = f(3) = 6, g(3) = f(5) = 10 \).

Creating the difference table for \(g\), we get

\[ \begin{array} {rrrrr} n & g(n) & D_1(n) & D_2(n) & D_3 (n) \\ 1 & 3 & 3 & 1 \\ 2 & 6 & 4& \\ 3 & 10 & & \\ \end{array} \]

Hence, we obtain \( g(x) = 3 + \frac{3}{1!} (x-1) + \frac{1}{2!} (x-1)(x-2) = \frac{ (x+1)(x+2) } { 2} \). Finally, since \( f( 2x - 1) = g(x) \), with the substitution \( x = \frac{y+1}{2} \), we get

\[ f(y) = f(2x-1) = g(x) = \frac{ (x+1)(x+2) } { 2 } = \frac{ \left( \frac{y+1}{2} + 1\right) \left( \frac{y+1}{2} + 2 \right) } { 2 } = \frac{ (y+3)( y + 5) } { 8 }. \ _\square \]

Prove that there is no polynomial (of finite degree) which satisfies \( f(n) = 2^n \) for all positive integers.

---

Construct the difference table for \( f(n) = 2^n \). Since \( D_1(n) = f(n+1) - f(n) = 2^{n+1} - 2^{n} = 2^{n}=f(n) \), we see that \(D_1 \) is exactly equal to \(f \). This remains true for each \(k^\text{th}\) difference column, which means that the \(k^\text{th}\) difference column is never a constant. Hence there is no polynomial of degree \(k\) that satisfies \(f(n) = 2^n \). \(_\square\)

Prove that there is no polynomial (of finite degree) which satisfies \( f(n) = F_n \) for all positive integers, where \(F_n\) is the \(n\)th Fibonacci Number.

---

Construct the difference table for \( f(n) = F_n \). Since \( D_1(n) = f(n+1) - f(n) = F_{n+1} - F_n = F_{n-1} \), we see that \(D_1 (n) \) is exactly equal to \(F_{n-1}\).

Similarly, \( D_2 (n) = D_1 (n+1) - D_1 (n) = F_n - F_{n-1} = F_{n-2} \).

In general, \( D_k (n) = F_{n-k} \).

In particular, this shows that the \(k^\text{th}\) difference column is never a constant. Hence there is no polynomial of degree \(k\) that satisfies \(f(n) = F_n \). \(_\square\)

1) Use the method of finite difference to find the general term of the following sequence:

\[ 0, 6, 34, 102, 228, \ldots. \]

2) What comes next?

\[ 1, 2, 4, 7, 11, 16, \text{____} \]