Higher Order Differences

# Higher Order Differences

Recall from The Difference Operator that if $f$ is a real-valued function then $\Delta f(x) = f(x + 1) - f(x)$. We will now look at higher orders of the difference operator $\Delta$.

 Definition: If $f$ is a real-valued function then the $p^{\mathrm{th}}$ Order Difference of $f$ denoted $\Delta^p f$ is defined to be $\Delta^p f(x) = \Delta^{p-1} f(x + 1) - \Delta^{p-1} f(x)$.

For example, if $f(x) = x^2 + 2x - 1$ then the first, second, and third ordered differences of $f$ denoted $\Delta f$, $\Delta^2 f$, and $\Delta^3 f$ respectively are:

(1)
\begin{align} \quad \Delta f = \Delta (x^2 + 2x - 1) = \left ( (x + 1)^2 + 2(x + 1) - 1 \right ) - \left (x^2 + 2x - 1 \right ) = x^2 + 2x + 1 + 2x + 2 - 1 - x^2 - 2x + 1 = 2x + 3 \end{align}
(2)
\begin{align} \quad \Delta^2 f = \Delta (\Delta f) = \Delta (2x + 3) = \left ( 2(x + 1) + 3 \right ) - \left ( 2x + 3 \right ) = 2x + 2 + 3 - 2x - 3 = 2 \end{align}
(3)
\begin{align} \quad \Delta^3 f = \Delta^2 (\Delta f) = \Delta (\Delta^2 f) = \Delta (2) = 2 - 2 = 0 \end{align}

As you can see, to determine $\Delta^p f$, it appears we need to compute $\Delta f$, $\Delta^2 f$, …, $\Delta^{p-1} f$. Interestingly enough, higher order differences seem to follow a pattern. Notice that:

(4)
\begin{align} \quad \Delta f = f(x + 1) - f(x) \end{align}
(5)
\begin{align} \quad \Delta^2 f = \Delta ( \Delta f) = \Delta (f(x+1) - f(x)) = f(x+2) - f(x+1) - f(x+1) + f(x) = f(x + 2) - 2f(x + 1) + f(x) \end{align}
(6)
\begin{align} \quad \Delta^3 f = \Delta (\Delta^2 f) = \Delta (f(x + 2) - 2f(x+1) + f(x)) = f(x + 3) - 2f(x+2) + f(x+1) - f(x+2) + 2f(x+1) - f(x) = f(x+3) -3f(x+2) + 3f(x+1) - f(x) \end{align}

Notice the coefficients on $\Delta f$, $\Delta^2 f$, and $\Delta^3 f$. It appears as though the binomial coefficients are appear. Furthermore, we note that the terms are alternating from positive to negative. We generalize this observation in the following theorem.

 Theorem 1: If $f$ is a real-valued function and $p \in \{1, 2, ... \}$ then $\displaystyle{\Delta^p f(x) = \binom{p}{0}(-1)^p f(x) + \binom{p}{1} (-1)^{p-1} f(x + 1) + ... + \binom{p}{p-1} (-1) f(x + p - 1) + \binom{p}{p} f(x + p) = \sum_{k=0}^{p} \binom{p}{k} (-1)^{p-k} f(x + k)}$.
• Proof: Let $S, T$ be operators where $S(f(x)) = f(x + 1)$ and $T(f(x)) = f(x)$. Then $S^p (f(x)) = f(x + p)$ and $T^p (f(x)) = f(x)$. Note that $\Delta = (S - T)$ and $\Delta^p = (S - T)^p$. Therefore:
(7)
\begin{align} \quad \Delta^p = (S - T)^p \end{align}

*

(8)
\begin{align} \quad \Delta^p = (S - T)^p = \binom{p}{0} S^0(-T)^p + \binom{p}{1}S^{1}(-T)^{p-1} + ... + \binom{p}{p-1}S^{p-1}(-T)^{1} + \binom{p}{p} S^p(-T)^0 = \sum_{k=0}^{p} \binom{p}{k} S^{k}(-T)^{p-k} = \sum_{k=0}^{p} \binom{p}{k} (-1)^{p-k} S^{k}T^{p-k} \end{align}
• Applying $\Delta^p$ to a real-valued function $f$ yields us:
(9)
\begin{align} \quad \Delta^p (f(x)) = \sum_{k=0}^{p} \binom{p}{k} (-1)^{p-k} S^{k}T^{p-k} f(x) \\ \quad \Delta^p (f(x)) = \sum_{k=0}^{p} \binom{p}{k} (-1)^{p-k} S^k (f(x)) \\ \quad \Delta^p (f(x)) = \sum_{k=0}^{p} \binom{p}{k} (-1)^{p-k} f(x + k) \quad \blacksquare \end{align}