Proposition 4.1.4
A sequence \(f(n)\) is given by a polynomial of degree \(\le d\) if and only if
\[
\sum_{n\ge 0} f(n)z^n
=
\frac{h(z)}{(1-z)^{d+1}}
\]
for some polynomial \(h(z)\) of degree \(\le d\). Furthermore, \(f(n)\) has degree \(d\) if and only if \(h(1)\neq 0\).
Proof
Suppose \(f(n)\) is a polynomial of degree \(\leq d\). By Proposition 4.1.3, we can write \(f(n)\) in the \(\Delta\)-basis:
$$
\begin{align*}
f(n) = \sum_{m=0}^d f^{(m)} \binom{n}{m}
\end{align*}
$$
If we multiply by \(z^n\) and then sum over all \(n \geq 0\)
$$
\begin{align*}
\sum_{n \geq 0} f(n)z^n &= \sum_{n\geq 0} \left(\sum_{m=0}^d f^{(m)} \binom{n}{m} z^n \right) \\
&= \sum_{n \geq 0} \left( f^{(0)} \binom{n}{0} z^n + f^{(1)} \binom{n}{1} z^n + \cdots + f^{(d)} \binom{n}{d}z^n \right) \\
&= f^{(0)} \sum_{n \geq 0} \binom{n}{0} z^n + f^{(1)} \sum_{n \geq 0} \binom{n}{1} z^n + \cdots + f^{(d)} \sum_{n \geq 0} \binom{n}{d}z^n \\
&= \sum_{m=0}^d f^{(m)} \sum_{n \geq 0} \binom{n}{m} z^n \\
&= \sum_{m=0}^d f^{(m)} \frac{z^m}{(1-z)^{m+1}} \quad \text{(by 4.1.6)}
\end{align*}
$$
If we let \(h(z) = \sum_{m=0}^d f^{(m)} z^m (1-z)^{d-m}\), then \(h(z)\) is a polynomial of degree at most \(d\). Conversely, if \(h(z)\) is a polynomial of degree at most \(d\), then write \(h(z)\) in terms of the \((\gamma)\)-basis so
$$
\begin{align*}
h(z) = \sum_{m=0}^d a_m z^m (1-z)^{d-m}
\end{align*}
$$
Then
$$
\begin{align*}
F(z) &= \frac{h(z)}{(1-z)^{(d+1)}} \\
&= \frac{\sum_{m=0}^d a_m z^m (1-z)^{d-m}}{(1-z)^{(d+1)}} \\
&= \sum_{m=0}^d a_m z^m \frac{(1-z)^{(d-m)}}{(1-z)^{(d+1)}} \\
&= \sum_{m=0}^d a_m \frac{z^m}{(1-z)^{(m+1)}} \\
&= \sum_{m=0}^d a_m \sum_{n \geq 0} \binom{n}{m} z^n \quad \text{(by 4.1.6)} \\
&= \sum_{n \geq 0} \left( \sum_{m=0}^d a_m \binom{n}{m} \right) z^n \\
&= \sum_{n \geq 0} f(n) z^n.
\end{align*}
$$
Then \(f(n)\) is a linear combination of the \(\Delta\)-basis vectors. Hence by Proposition 4.1.3, it is of degree at most \(d\). \(\ \blacksquare\)