Real Analysis – Finding the Power Series of a Rational Function

combinatoricsgenerating-functionsreal-analysis

In many combinatorial enumeration problems it is possible to find a rational generating function (i.e. the quotient of two polynomials) for the sequence in question. The question is – given the generating function, how can we find (algorithmically) the values of the sequence, i.e. the coefficients of the corresponding power series?

I know that for a rational generating function, the sequence satisfies a recurrence relation given by the coefficients of the polynomial in the denominator, so it's really just the question of finding the finite initial values.

Best Answer

If $$f(x) = \frac{P(x)}{Q(x)}$$ where $P,Q$ are polynomials, then we have that

$$f(x)Q(x) = P(x)$$

Now use Leibniz's formula for differentiating a product

$$\sum_{r=0}^{n} {n \choose r} f^{r}(x) Q^{n-r}(x) = P^{n}(x)$$

which you can evaluate at $0$ for $n=1,2,\dots$ and you can obtain $(n+1)^{th}$ derivative of $f$ at $0$ from the first $n$ derivatives using the above formula.

The coefficient you need would be $\frac{f^{n}(0)}{n!}$.

This should be easily doable by a computer. No integration etc needed.

Related Question