*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:
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 .