Difference Tables

From Math Images

This is a Helper Page for:
Fibonacci Numbers
Prime spiral (Ulam spiral)

A difference table is made by listing the terms of a sequence and its differences. It includes the first differences, which is a sequence that lists the differences of two consecutive terms of the original sequence. For instance, the first term of the first differences is the difference between the first and second term of the original sentence, the second term of the first difference is the difference between the second and third term of the original sentence, and so forth.

Second-order differences, which is a sequence of differences of the first differences, and other higher-order differences can also be included in the difference table.

An important thing to notice is that we find the differences by subtracting the earlier term from the later term of the sequence and not by subtracting the term with the smaller value from the term with the larger value. Thus, it is possible to have a negative number in the difference table.

For example, let's create a difference table for the sequence of perfect squares :

$0, 1, 4, 9, 16,25, 36,\dots$

First, list the terms of the sequence on the top row. Then write each difference of two consecutive terms underneath and in between the terms it is the difference of. For instance, the terms $1, 3, 5, 7, \dots$ in the first differences are found by $1-0=1, 4-1=3, 9-4=5, 16-9=7, \dots$ . We can also create another row of second-order differences that lists the differences of two consecutive terms from the first sequence of differences.

As we can see from this difference table, the last row of third-degree differences consists of $0$ 's that continue infinitely. Indeed, all polynomial sequences generate a row of only $0$ 's at some level of the difference table. Every sequence that eventually reduces to $0$ 's can be written as a polynomial sequence. Furthermore, there are some methods that we can use to determine the specific polynomial function.

We can find the polynomial function for an original sequence in two ways. The first method involves finding a general form of the function and substituting unknown values with some values from the sequence, and the second method uses the difference table and a formula involving factorials. Here, we use $x=0$ to define the first term of the sequence. Depending on the author, some books use $x=0$ and some use $x=1$ .

Using substitution

Using the first method, we can find a general form for the polynomial function by looking at the difference table. If a row with constant differences other than 0 appear on the $n$ th difference, then it implies that the original sequence can be determined by a $n$ th degree polynomial function, which will have the form :

$ax^n+bx^{n-1}+cx^{n-2}+\dots+\hbox{constant}$

We can find the values of the coefficients by plugging in some values for the unknown $x$ . For instance, let's look at the difference table for the sequence of perfect squares. The row of second differences gives a constant value; thus, we know that the original sequence can be described through a second degree polynomial :

$ax^2+bx+c$ .

The first term of the sequence is $0$ when $x=0$ , the second term is $1$ when $x=1$ , and the third term is $2$ when $x=4$ . Thus, plugging in these numbers we get :

$a (0)^2+b(0)+c=0$

$a(1)^2+b(1) + c =1$

$a(2)^2+b(2)+c=4$

Because we have three unknowns $a, b, c$ and three equations, we can find the value of $a, b, c$ to be :

$a=1$

$b=0$

$c=0$ .

Thus, we can find the polynomial expression for sequence $0, 1, 4, 9, 16 \dots$ to be $x^2$ for $x=0, 1, 2, 3, 4 \dots$ .

Using Newton's Interpolation Formula

Another way of determining the polynomial function is to use Newton's Interpolation Formula:

$p(x)=\sum_{k=0}^{\infty} \frac{{{\Delta}^k}p_0}{k!}x_{(k)}$

where $x_{(k)}$ is the $k$ th degree falling factorial polynomial

$\begin{matrix} \underbrace{x(x-1)(x-2) \dots (x-(k-1))} \\k\ \mbox{factors}\end{matrix}$

and ${{\Delta}^k} p_0$ indicates the leftmost value of the $k$ th difference in the difference table. In fact, the original sequence counts as the $0$ th difference.

If the original sequence (the first row of the difference table) is a polynomial sequence, then this form of Newton's Interpolation Formula will find that polynomial.

Let's find the polynomial for the sequence of perfect squares using the difference table given above.

$p(x)=\frac{{{\Delta}^0}p_0}{0!} x_{(0)}+\frac{{{\Delta}^1}p_0}{1!} x_{(1)}+\frac{{{\Delta}^2}p_0}{2!} x_{(2)}+\frac{{{\Delta}^3}p_0}{3!}+\frac{{{\Delta}^4}p_0}{4!}+\dots$

$=\frac{{{\Delta}^0}p_0}{0!} x_{(0)}+\frac{{{\Delta}^1}p_0}{1!} x_{(1)}+\frac{{{\Delta}^2}p_0}{2!} x_{(2)}$ [All further terms are 0]

$=\frac{0}{0!}+\frac{1}{1!}x+\frac{2}{2!}x(x-1)$

$=0+x+x^2-x$

$=x^2$

Thus, we found out that the original sequence is a sequence of perfect squares where the polynomial function is :

$f(x)=x^2$

The table below shows a difference table of the Fibonacci sequence.. Because Fibonacci numbers are not polynomials, they do not reach a row with only $0$ 's.