Lemma
If \(f(n) = \binom{n}{m}\), then
\(
F(z) = \sum_{n \geq 0} \binom{n}{m} z^n = \frac{z^m}{(1-z)^{m+1}}
\)
Proof
Since \(\binom{n}{m} = 0\) for \(n < m\), then we can re-write the sum as
$$
\begin{align*}
F(z) = \sum_{n \geq 0} \binom{n}{m} z^n = \sum_{n \geq m} \binom{n}{m} z^n
\end{align*}
$$
Expand the binomial term and pull \(\frac{1}{m!}\) out since it doesn’t depend on \(n\) to get
$$
\begin{align*}
F(z) &= \sum_{n \geq m} \left( \frac{n(n-1)\cdots(n-m+1)}{m!} \right) z^n \\
&= \frac{1}{m!} \sum_{n \geq m} n(n-1)\cdots(n-m+1) z^n
\end{align*}
$$
For all \(n \geq m\), we can write \(z^n = z^m z^{n-m}\). Hence
$$
\begin{align*}
F(z) &= \frac{z^m}{m!} \sum_{n \geq m} n(n-1)\cdots(n-m+1) z^{n-m} \tag{1}
\end{align*}
$$
But recall that the geometric series when \(|z| < 1\) evaluates to
$$
\begin{align*}
\sum_{n \geq 0} z^n = \frac{1}{1-z}
\end{align*}
$$
If we differentiate \(m\) times both sides, we get
$$
\begin{align*}
\sum_{n \geq m} n(n-1)\cdots (n-m+1) z^{n-m} = \left(\frac{d}{dz}\right)^m \frac{1}{1-z}
\end{align*}
$$
Substitute this back in (1) to see that
$$
\begin{align*}
F(z) &= \frac{z^m}{m!} \left(\frac{d}{dz}\right)^m \frac{1}{1-z} \tag{2}
\end{align*}
$$
But we also know that
$$
\begin{align*}
\left(\frac{d}{dz}\right)^m \frac{1}{1-z} = \frac{m!}{(1-z)^{m+1}}
\end{align*}
$$
If we substitute this in (2)
$$
\begin{align*}
F(z) &= \frac{z^m}{m!} \cdot \frac{m!}{(1-z)^{m+1}} \\
&=
\boxed{
\frac{z^m}{(1-z)^{m+1}}}
\end{align*}
$$
So now if we’re given any polynomial of degree \(\leq d\), then by proposition 4.1.2, we know we can re-write it in terms of the basis \(\Delta\).
$$
\begin{align*}
F(z) = \sum_{m = 0}^d f^{(m)} \binom{n}{m}
\end{align*}
$$
But now the lemma gives us the generating function of each basis vector:
$$
\begin{align*}
\sum_{n \geq 0} \binom{n}{m} z^n &= \frac{z^m}{(1-z)^{m+1}} \tag{1}
\end{align*}
$$
So if \(f(n) = n^2\), then instead of evaluating \(\sum_{n\geq 0} n^2 z^n\). We will first re-write \(n^2\) in the \(\Delta\) basis as follows
$$
\begin{align*}
n^2 = \binom{n}{1} + 2\binom{n}{2}
\end{align*}
$$
Then
$$
\begin{align*}
\sum_{n \geq 0} n^2z^n &= \sum_{n \geq 0} \left( \binom{n}{1} + 2\binom{n}{2} \right) z^n \\
&= \sum_{n \geq 0} \binom{n}{1}z^n + 2\sum_{n \geq 0} \binom{n}{2} z^n \\
&= \frac{z}{(1-z)^2} + 2 \frac{z^2}{(1-z)^3}
\end{align*}
$$
References