Proposition 4.1.3
A sequence \(f(n)\) is given by a polynomial of degree \(\le d\) if and only if \((\Delta^m f)(0)=0
\) for all \(m>d\).
Given a sequence \(f: \mathbb{N} \to \mathbb{C}\). Recall that
$$
\begin{align*}
(If)(n) &:= f(n) \quad \text{(identity operator)} \\
(\Delta f)(n) &:= f(n+1)-f(n) \quad \text{difference operator)} \\
(Sf)(n) &:= f(n+1) \quad \text{(shift operator)}
\end{align*}
$$
So if we have a sequence \((0,1,4,9,16,25\cdots)\), then \(S^4f = (16,25,36,\cdots)\). So \((S^4f)(0) = 16\). Moreover
$$
\begin{align*}
(\Delta f)(0) &= f(1) - f(0) = 1-0=1 \\
(\Delta f)(1) &= f(2) - f(1) = 4-1=3 \\
(\Delta f)(2) &= f(3) - f(2) = 9-4=5 \\
(\Delta f)(3) &= f(4) - f(3) = 16-9=7
\end{align*}
$$
So \(\Delta f = (1,3,5,7,\cdots)\) or
$$
\begin{align*}
(\Delta f)(n) = (n+1)^2 - n^2 = n^2 + 2n + 1 - n^2 = 2n + 1.
\end{align*}
$$
and
$$
\begin{align*}
(\Delta^2 f)(n) &= (\Delta f)(n+1) - (\Delta f)(n) \\
&= (2(n+1)+1) - (2n+1) \\
&= 2n+3-2n-1 = 2. \\
(\Delta^3 f)(n) &= (\Delta^2 f)(n+1) - (\Delta^2 f)(n) \\
&= 2 - 2 = 0.
\end{align*}
$$
Hence the difference operator measures the change in the sequence between consecutive terms.
Proof
The \(n\)th term of the sequence is obtained by shifting the sequence left by \(n\) terms and then taking the \(0\)th term so \(f(n)=(S^n f)(0)\). Now suppose that \((\Delta^m f)(0)=0\) for all \(m > d\). We know that \(S = I + \Delta\). Hence
$$
\begin{align*}
f(n) &= (S^n f)(0) \\
&= ((I + \Delta)^nf)(0) \\
&= \left( \sum_{m = 0}^n \binom{n}{m} \Delta^m f \right)(0) \\
&=\sum_{m=0}^{n} \binom{n}{m} (\Delta^m f)(0) \\
&=\sum_{m=0}^{d} \binom{n}{m} (\Delta^m f)(0).
\end{align*}
$$
which is a polynomial of degree \(\le d\). Conversely, if \(f(n)\) is a polynomial of degree \(\le d\), then we can express it
in terms of the \((\Delta)\)-basis:
$$
f(n)=\sum_{m=0}^{d}\alpha_m \binom{n}{m}
$$
for some \(\alpha_0,\alpha_1,\dots,\alpha_d\in\mathbb C\). Recall Pascal’s identity: \(\binom{n+1}{m} = \binom{n}{m} + \binom{n}{m-1}\).
Hence
$$
\begin{align*}
\Delta\binom{n}{m} &= \binom{n+1}{m} - \binom{n}{m} = \binom{n}{m-1}.
\end{align*}
$$
Therefore,
$$
\begin{align*}
\Delta f
=
\sum_{m=1}^{d}\alpha_m \binom{n}{m-1},
\end{align*}
$$
which is a polynomial of degree \(\le d-1\). By Induction, we can further show that \(\Delta^m f=0\) for all \(m>d\). \(\blacksquare\)
Recall again that we can write the sequence as
$$
\begin{align*}
f(n) &= \sum_{m=0}^{d} \binom{n}{m} (\Delta^m f)(0) \\
&= \binom{n}{0} (\Delta^0 f)(0) + \binom{n}{1} (\Delta^1 f)(0) + \cdots + \binom{n}{d} (\Delta^d f)(0)
\end{align*}
$$
As noted in the textbook, the proof shows \((\Delta^m f)(0)\) are the coefficients of the polynomial \(f(n)\) when expressed in terms of the \(\Delta\) basis. To simplify the notation, let \(f^{(m)} = (\Delta^m f)(0)\). So
$$
\begin{align*}
f(n) &= f^{(0)}\binom{n}{0} + f^{(1)}\binom{n}{1} + \cdots + f^{(d)}\binom{n}{d}
\end{align*}
$$
When \(f(n) = n^2\) for example, \(f^{(0)} = 0, f^{(1)} = 1, f^{(2)} = 2\) and so
$$
\begin{align*}
n^2 &= \binom{n}{1} + 2\binom{n}{2}
\end{align*}
$$
References