Lesson 8

As in the above example, in many cases the generating function turns out to be rational, i.e., the ratio of two polynomials. For convenient computation of derivatives of such functions, they can be expanded into a sum of simplest fractions (this technique also helps in integrating such functions). This is done using the method of undetermined coefficients.

Theorem. Let \(p(x)\) be a polynomial of degree less than \(t\), and \(\alpha_{1}, \dotsc, \alpha_{t}\) be (pairwise) distinct nonzero numbers. Then there exist numbers \(c_{1}, \dotsc, c_{t}\) such that \[\mathcal{P}(x)=\frac{p(x)}{(1-\alpha_1x)\dotsb(1-\alpha_tx)}=\frac{c_1}{1-\alpha_1x}+\dotsb+\frac{c_t}{1-\alpha_tx}\ .\] (Thus, \(\alpha_{1}, \dotsc, \alpha_{t}\) are reciprocals of the roots of the denominator.)

If \(\alpha\) is the reciprocal of a root of the denominator of multiplicity \(m\) (i.e., the denominator has a factor \((1-\alpha x)^{m}\)), then the right-hand side will have terms of the form \(\frac{c}{(1-\alpha x)^k}\) for all \(1 \le k \le m\).

Having such a decomposition into simplest fractions, we can easily expand \(\mathcal{P}(x)\) into a series: \[\mathcal{P}(x)=\sum_{n=0}^{\infty}(c_{1}\alpha_{1}^{n}+\dotsb+c_{t}\alpha_{t}^{n})x^{n}\] (since \(\frac{1}{1-\alpha x}=\sum_{n=0}^{\infty}\alpha^{n}x^{n}\)).

We will not formally prove this theorem. The method is as follows: bring the left and right sides to a common denominator and obtain an equality of two polynomials of degree at most \(t\). By equating their coefficients at corresponding powers of \(x\), we find the constants \(c_{1}, \dotsc, c_{t}\) by solving the corresponding system of linear equations. (In practice, simpler linear equations may result if we equate not coefficients, but values of the polynomials at the same point.)