*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 . This is a rational function and we are asked the question: *How do we extract its coefficients*?

We denote by the coefficient of in . We will also denote for brevity. First off, we note that and so surely their coefficients must agree, that is, . The right-hand side is obviously zero if , so keeping this in mind, let us manipulate the equation a bit.

It should be fairly obvious that . Also, the operator turns out to be linear in its second argument (this is also not difficult to show). So our previous equation suddenly becomes for all , but now we apply our previous remark; this gives for all . Applying the definition of this gives the nice recurrence . This is called a homogeneous recurrence because the constant is zero.

OK, but this doesn’t *uniquely* determine the function . We have a recurrence satisfied whenever , but what about when is 0, 1, or 2? We have to *specify* these alongside the recurrence in order to get rid of the ambiguity. First, we find , by evaluating . As for the other two, they can be determined from the equation , by splitting it up as before (we obtain, for example, and hence ).

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

Let and be sequences with generating series and respectively, and suppose there exist constants such that

for all .

Then there are polynomials and such that is invertible as a power series and .

**Information loss**. As I said previously, we should note that in passing to the recurrence we have *lost* information about the generating function, which can not be recovered unless we are supplied with initial conditions . So suppose we are given . We can try to reassemble it:

for all

and hence

for all

Hmm. So obviously from this we can conclude that the right-hand side must have been a polynomial of degree at most 2. Say . We get

(for all ).

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

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

### Like this:

Like Loading...

*Related*

## About mlbaker

just another guy trying to make the diagrams commute.