## Recurrences and rational generating series

*sips tea* Alright, so it’s 4:00 AM and I can’t sleep yet again, so I’m here to ramble on about rational generating functions and the recurrences they give rise to.

Example. Consider the generating function given by $F(x) = \frac{5-x}{1-2x-x^2+2x^3}$. This is a rational function and we are asked the question: How do we extract its coefficients?

We denote by $\langle x^n, F(x) \rangle$ the coefficient of $x^n$ in $F(x)$. We will also denote $f_n = \langle x^n, F(x) \rangle$ for brevity. First off, we note that $(1-2x-x^2+2x^3)F(x) = 5-x$ and so surely their coefficients must agree, that is, $\langle x^n, (1-2x-x^2+2x^3)F(x) \rangle = \langle x^n, 5-x \rangle$. The right-hand side is obviously zero if $n \geq 2$, so keeping this in mind, let us manipulate the equation a bit.

It should be fairly obvious that $\langle x^n, x^kF(x) \rangle = \langle x^{n-k}, F(x) \rangle$. Also, the operator $\langle \cdot, \cdot \rangle$ turns out to be linear in its second argument (this is also not difficult to show). So our previous equation suddenly becomes $\langle x^n, F(x) \rangle - 2 \langle x^n, xF(x) \rangle - \langle x^n, x^2F(x) \rangle + 2 \langle x^n, x^3F(x) \rangle = 0$ for all $n \geq 2$, but now we apply our previous remark; this gives $\langle x^n, F(x) \rangle - 2 \langle x^{n-1}, F(x) \rangle - \langle x^{n-2}, F(x) \rangle + 2 \langle x^{n-3}, F(x) \rangle = 0$ for all $n \geq 3$. Applying the definition of $f_n$ this gives the nice recurrence $f_n - 2f_{n-1} - f_{n-2} + 2f_{n-3} = 0$. This is called a homogeneous recurrence because the constant is zero.

OK, but this doesn’t uniquely determine the function $F(x)$. We have a recurrence satisfied whenever $n \geq 3$, but what about when $n$ is 0, 1, or 2? We have to specify these alongside the recurrence in order to get rid of the ambiguity. First, we find $f_0 = 5$, by evaluating $F(0)$. As for the other two, they can be determined from the equation $\langle x^n, (1-2x-x^2+2x^3)F(x) \rangle = \langle x^n, 5-x \rangle$, by splitting it up as before (we obtain, for example, $f_1 - 2f_0 = -1$ and hence $f_1 = 9$).

General result: (it is a routine exercise to prove this)

Let $(f_n)_{n \geq 0}$ and $(g_n)_{n \geq 0}$ be sequences with generating series $F(x)$ and $G(x)$ respectively, and suppose there exist constants $a_1, \ldots, a_k$ such that

$f_n + a_1f_{n-1} + \ldots + a_kf_{n-k} = g_n$ for all $n \geq k$.

Then there are polynomials $a(x)$ and $b(x)$ such that $a(x)$ is invertible as a power series and $a(x)F(x) = G(x) + b(x)$.

Information loss. As I said previously, we should note that in passing to the recurrence $f_n - 2f_{n-1} - f_{n-2} + 2f_{n-3} = 0$ we have lost information about the generating function, which can not be recovered unless we are supplied with initial conditions $f_0, f_1, f_2$. So suppose we are given $f_0, f_1, f_2$. We can try to reassemble it:

$\langle x^n, F(x) \rangle - 2 \langle x^{n-1}, F(x) \rangle - \langle x^{n-2}, F(x) \rangle + 2 \langle x^{n-3}, F(x) \rangle = 0$ for all $n \geq 3$

and hence

$\langle x^n, (1 - 2x - x^2 + 2x^3)F(x) \rangle = 0$ for all $n \geq 3$

Hmm. So obviously from this we can conclude that the right-hand side must have been a polynomial $p(x)$ of degree at most 2. Say $p(x) = a + bx + cx^2$. We get

$\langle x^n, (1-2x-x^2+2x^3)F(x) \rangle = \langle x^n, a+bx+cx^2 \rangle$ (for all $n$).

working with the equation some more and using common sense to guide us, we get

$f_0 = a$, $f_1 - 2f_0 = b$, etc. In this way, plugging back in the initial conditions, we can solve for the right-hand side, and hence reform the rational generating function $F(x)$.