Proposition 4.1.5
Let \((f(n))_{n\ge0}\) be a sequence of numbers. Then \((f(n))_{n\ge0}\) satisfies a linear recurrence of the form (4.1.10) (with \(c_0,c_d\neq0\)) if and only if
\[
F(z)=\sum_{n\ge0} f(n)z^n
=\frac{p(z)}{c_d z^d+c_{d-1}z^{d-1}+\cdots+c_0}
\]
for some polynomial \(p(z)\) of degree \(< d\).
So in proposition 4.1.4, given a polynomial sequence, we see that the generation function is a rational function but now given any sequence of numbers. if the sequence satisfies a linear recurrence of the above form, then the generation function is also a rational function. Consider the following example:
Suppose we have a sequence satisfies the recurrence
$$
\begin{align*}
f(n)-3f(n-1)+2f(n-2)=0. \tag{1}
\end{align*}
$$
when \(n \geq 2\). Let
$$
\begin{align*}
F(z)=\sum_{n\ge 0} f(n)z^n
=f(0)+f(1)z+f(2)z^2+f(3)z^3+\cdots.
\end{align*}
$$
Multiply by the polynomial with coefficients matching the recurrence, \((1-3z+2z^2)F(z)\). Expanding gives
$$
\begin{align*}
(1-3z+2z^2)F(z)
&=\bigl(f(0)+f(1)z+f(2)z^2+f(3)z^3+\cdots\bigr) \\
&\quad+\bigl(-3f(0)z-3f(1)z^2-3f(2)z^3-\cdots\bigr) \\
&\quad+\bigl(2f(0)z^2+2f(1)z^3+2f(2)z^4+\cdots\bigr).
\end{align*}
$$
Collecting like powers of \(z\), we obtain
$$
\begin{align*}
(1-3z+2z^2)F(z)
&=f(0) \\
&\quad+\bigl(f(1)-3f(0)\bigr)z \\
&\quad+\bigl(f(2)-3f(1)+2f(0)\bigr)z^2 \\
&\quad+\bigl(f(3)-3f(2)+2f(1)\bigr)z^3 \\
&\quad+\cdots .
\end{align*}
$$
Hence, the coefficient of \(z^n\) is
$$
\begin{align*}
f(n)-3f(n-1)+2f(n-2).
\end{align*}
$$
By (1), this coefficient is zero for all \(n\ge 2\). Therefore,
$$
\begin{align*}
(1-3z+2z^2)F(z)
=
f(0)+\bigl(f(1)-3f(0)\bigr)z,
\end{align*}
$$
which is a polynomial. Consequently,
$$
\begin{align*}
F(z)
=
\frac{f(0)+\bigl(f(1)-3f(0)\bigr)z}
{1-3z+2z^2},
\end{align*}
$$
so \(F(z)\) is a rational function.
Proof
Let \((f(n))_{n\ge0}\) be a sequence of numbers that satisfies a recurrence of the form
$$
\begin{align*}
c_0 f(m+d) + c_1 f(m+d-1) + \cdots + c_d f(m) = 0. \tag{4.1.10}
\end{align*}
$$
where \(c_0,c_d \neq 0\). Let \(F(z) = \sum_{n \geq 0} f(n)z^n\) and let \(q(z) = c_0 + c_1 z + c_2 z^2 + \cdots + c_d z^{d}\) be the polynomial whose coefficients match the recurrence coefficients. Since \(c_d \neq 0\), then \(q(z)\) is of degree \(d\). Next, compute \(q(z)F(z)\) as follows
$$
\begin{align*}
q(z)F(z) &= (c_0 + c_1 z + c_2 z^2 + \cdots + c_d z^{d} )F(z) \\
&= c_0F(z) +c_1zF(z) +\cdots +c_dz^dF(z)
\end{align*}
$$
if we expand each term, we get
$$
\begin{align*}
q(z)F(z) &= c_0f(0) + c_0f(1)z + \cdots + c_0f(n)z^n + \cdots \\
& + c_1f(0)z + c_1f(1)z^2 + \cdots + c_1f(n-1)z^n + \cdots \\
& + c_2f(0)z^2 + c_2f(1)z^3 + \cdots + c_2f(n-2)z^n + \cdots \\
&+ \cdots \\
&+ c_df(0)z^d + c_df(1)z^{d+1} + \cdots + c_df(n-d)z^n + \cdots.
\end{align*}
$$
For \(n\ge d\), the coefficient of \(z^n\) is
$$
\begin{align*}
c_0f(n) + c_1f(n-1) + c_2f(n-2) + \cdots + c_df(n-d) \tag{2}
\end{align*}
$$
Since \(n\ge d\), we have \(m=n-d\ge0\). Setting
\(m=n-d\) into (4.1.10) gives
$$
\begin{align*}
c_0 f(n) + c_1 f(n-1) + \cdots + c_d f(n-d) = 0.
\end{align*}
$$
But this is exactly the coefficient of \(z^n\) in \((1)\). Therefore, every coefficient of \(z^n\) where \(n \geq d\) vanishes. Hence \(q(z)F(z)\) has no terms of degree \(d\) or higher. Therefore, \(q(z)F(z)\) is a polynomial of degree at most \(d-1\). Define \(p(z)=q(z)F(z).\)
Then \(p\) is of degree \(< d\) and
$$
\begin{align*}
F(z)=\frac{p(z)}{q(z)}
=
\frac{p(z)}
{c_0+c_1z+\cdots+c_dz^d}.
\end{align*}
$$
Conversely, suppose that
$$
\begin{align*}
F(z)=\sum_{n\ge0} f(n)z^n
=\frac{p(z)}{q(z)} \tag{2}
\end{align*}
$$
where \(q(z) = c_0 + c_1 z + c_2 z^2 + \cdots + c_d z^{d}\) and \(p(z)\) is a polynomial of degree \(< d\). \((2)\) gives
$$
\begin{align*}
q(z)F(z) = p(z)
\end{align*}
$$
Hence \(q(z)F(z)\) is of degree \(< d\). Hence we have no terms of degree \(d\) or higher. But recall that for \(n\ge d\), the coefficient of \(z^n\) in \(q(z)F(z)\) was computed previously to be
$$
\begin{align*}
c_0f(n) + c_1f(n-1) + c_2f(n-2) + \cdots + c_df(n-d)
\end{align*}
$$
Since we have no terms where \(n \geq d\), then
$$
\begin{align*}
c_0f(n)+c_1f(n-1)+\cdots+c_df(n-d)=0.
\end{align*}
$$
when \(n \geq d\). Setting \(n=m+d\) where \(m\ge0\) gives
$$
\begin{align*}
c_0f(m+d)+c_1f(m+d-1)+\cdots+c_df(m)=0.
\end{align*}
$$
Hence \((f(n))_{n\ge0}\) satisfies a linear recurrence of the form (4.1.10). \(\ \blacksquare\)
References