# Difference Tables of Sequences

Recall from the Difference Sequences page that if $(a_i)_{i=0}^{\infty} = (a_0, a_1, a_2, ...)$ is a sequence of real numbers then the first order difference sequence of $(a_i)_{i=0}^{\infty}$ is the sequence $(\Delta a_i)_{i=0}^{\infty}$ where $\Delta a_i = a_{i+1} - a_i$.

We also defined the $p^{\mathrm{th}}$ order difference sequence of $(a_i)_{i=0}^{\infty}$ to be $(\Delta^p a_i)_{i=0}^{\infty}$ where $\Delta^p a_i = \Delta^{p-1} a_{i+1} - \Delta^{p-1} a_i$.

We will now look at some more sequences of real numbers, $(a_i)_{i=0}^{\infty}$ and various $p^{\mathrm{th}}$ order difference sequences of $(a_i)_{i=0}^{\infty}$ and look at constructing their difference tables.

Definition: Let $(a_i)_{i=0}^{\infty}$ be a sequence of real numbers. Then the Difference Table of $(a_i)_{i=0}^{\infty}$ is a table of all entries of $(a_i)_{i=0}^{\infty}$, then all entries of $(\Delta a_i)_{i=0}^{\infty}$ underneath, then all entries of $(\Delta^2 a_i)_{i=0}^{\infty}$ underneath, etc… |

For example, consider the following sequence of real numbers and some of its difference sequences:

(1)The corresponding difference table for $(i^2 + 2)_{i=0}^{\infty}$ is therefore:

The first row of the difference table corresponds to the terms of $(i^2 + 2)_{i=0}^{\infty}$ and in general, the $p^{\mathrm{th}}$ row of a difference table corresponds to the terms of $(\Delta^p a_i)_{i=0}^{\infty}$.

Notice how in our example above we had that $\deg (i^2 + 2) = 2$ and $(\Delta^3 (i^2 + 2))_{i=0}^{\infty} = (0, 0, 0, ...)$. As we will see in the following theorem, if $q = q(i)$ is a polynomial with $\deg q < p$ then $(\Delta^p (q))_{i=0}^{\infty} = (0, 0, 0, ...)$.

Theorem 1: Let $q = q(i)$ be a polynomial where $\deg q < p$. Then $\Delta^p (q(i)) = 0$. |

**Proof:**If $q(i) = 0$ is the zero function then $\deg q = -\infty$ and clearly $\Delta (0) = (0 - 0) = 0$. Assume that $q(i) \neq 0$. We will carry the rest of this proof out by induction.

- Suppose that $\deg q = 0$. Then $q(i) = a_0$ where $a_0 \in \mathbb{R} \setminus \{ 0 \}$, and:

- Therefore Theorem 1 holds for all constant functions.

- For $p > 0$, suppose that for all polynomials $q$ with $\deg q < p$ we have that $\Delta^{p} (q) = 0$. We want to then show that for all polynomials $q$ with $\deg q = p$ we have that $\Delta^{p+1} (q) = 0$. Let $\deg q = p$. Then for $a_0, a_1, ..., a_p \in \mathbb{R}$ and $a_p \neq 0$, $q$ is of the form:

- Consider the function $\Delta (q(i)) = q(i+1) - q(i)$:

- Look at the term $(i + 1)^p$. By The Binomial Theorem we have that the expansion of this binomial term is:

- We have that $\binom{p}{0} = 1$, so the coefficient on $x^p$ in the expansion and simplification of the binomial $(i + 1)^p$ is $1$, so:

- Therefore $\deg \Delta (q(i)) = \deg (q(i+1) - q(i)) < p$ and so by our induction hypothesis we have that:

- Therefore by the principle of mathematical induction we have that for all polynomials $q = q(i)$ where $\deg q < p$ we have that $\Delta^{p} (q) = 0$. $\blacksquare$