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).


About mlbaker

just another guy trying to make the diagrams commute.
This entry was posted in combinatorics and tagged , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s