Difference Tables of Sequences

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)
\begin{align} \quad (i^2 + 2)_{i=0}^{\infty} = (2, 3, 6, 11, 18, 27, 38, ...) \end{align}
(2)
\begin{align} \quad (\Delta (i^2 + 2))_{i=0}^{\infty} = ((i + 1)^2 + 2 - i^2 - 2)_{i=0}^{\infty} = (i^2 + 2i + 1 - i^2)_{i=0}^{\infty} = (2i + 1)_{i=0}^{\infty} = (1, 3, 5, 7, 9, 11, ...) \end{align}
(3)
\begin{align} \quad (\Delta^2 (i^2 + 2))_{i=0}^{\infty} = (\Delta (2i + 1))_{i=0}^{\infty} = (2(i + 1) + 1 - 2i - 1)_{i=0}^{\infty} = (2i^0)_{i=0}^{\infty} = (2, 2, 2, 2, 2, 2, ...) \end{align}
(4)
\begin{align} \quad (\Delta^3 (i^2 + 2))_{i=0}^{\infty} = (2i^0)_{i=0}^{\infty} = (0)_{i=0}^{\infty} = (0, 0, 0, 0, 0, 0, ...) \end{align}

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

Screen%20Shot%202015-08-22%20at%209.52.07%20PM.png

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:
(5)
\begin{align} \quad \Delta (q) = \Delta (a_0) = (a_0 - a_0) = 0 \end{align}
  • 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:
(6)
\begin{align} \quad q(i) = a_0 + a_1i+ a_2i^2 + ... + a_pi^p \end{align}
  • Consider the function $\Delta (q(i)) = q(i+1) - q(i)$:
(7)
\begin{align} \quad \Delta (q(i)) = q(i+1) - q(i) = a_0 + a_1(i + 1) + a_2(i+1)^2 + ... + a_p(i + 1)^p - \left ( a_0 + a_1i + a_2i^2 + ... + a_pi^p) \right ) \end{align}
  • Look at the term $(i + 1)^p$. By The Binomial Theorem we have that the expansion of this binomial term is:
(8)
\begin{align} \quad (i + 1)^p = \binom{p}{0} i^p + \binom{p}{1} i^{p-1} + ... + \binom{p}{p-1} i + \binom{p}{p} \end{align}
  • 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:
(9)
\begin{align} \quad \Delta (q(i)) = q(i+1) - q(i) = a_0 + a_1(i + 1) + a_2(i+1)^2 + ... + a_p \left [\binom{p}{0}i^p + \binom{p}{1} i^{p-1} + ... + \binom{p}{p} \right ] - \left (a_0 + a_1i + a_2i^2 + ... + a_p i^p \right )\\ \end{align}
  • Therefore $\deg \Delta (q(i)) = \deg (q(i+1) - q(i)) < p$ and so by our induction hypothesis we have that:
(10)
\begin{align} \quad 0 \overset{I.H.} = \Delta^{p} (q(i+1) - q(i)) = \Delta^{p} (\Delta (q(i)) = \Delta^{p+1} (q(i)) \end{align}
  • 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$
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License