15.3: Partial Fractions

We got a simple solution to the seemingly impossible counting problem of Section 15.2.6 because its generating function simplified to the expression \(1/(1-x)^2\), whose power series coefficients we already knew. You’ve probably guessed that this problem was contrived so the answer would work out neatly. But other problems may not be so neat. To solve more general problems using generating functions, we need ways to find power series coefficients for generating functions given as formulas. Maclaurin’s Theorem 15.2.1 is a very general method for finding coefficients, but it only applies when formulas for repeated derivatives can be found, which isn’t often. However, there is an automatic way to find the power series coefficients for any formula that is a quotient of polynomials, namely, the method of partial fractions from elementary calculus.

The partial fraction method is based on the fact that quotients of polynomials can be expressed as sums of terms whose power series coefficients have nice formulas. For example when the denominator polynomial has distinct nonzero roots, the method rests on

Lemma 15.3.1. Let \(p(x)\) be a polynomial of degree less than \(n\) and let \(\alpha_1, \ldots, \alpha_n\) be distinct, nonzero numbers. Then there are constants \(c_1, \ldots, c_n\) such that

\[\nonumber \dfrac{p(x)}{(1-\alpha_1 x)(1-\alpha_2 x) \cdots (1-\alpha_n x)} = \dfrac{c_1}{1 - \alpha_1 x} + \dfrac{c_2}{1 - \alpha_2 x} + \cdots + \dfrac{c_n}{1 - \alpha_n x}.\]

Let’s illustrate the use of Lemma 15.3.1 by finding the power series coefficients for the function

\[\nonumber R(x) ::= \dfrac{x}{1 - x - x^2}.\]

We can use the quadratic formula to find the roots \(r_1, r_2\) of the denominator, \(1 - x - x^2\).

\[\nonumber r_1 = \dfrac{-1 - \sqrt{5}}{2}, r_2 = \dfrac{-1 + \sqrt{5}}{2}.\]

So

\[\nonumber 1 - x - x^2 = (x - r_1)(x - r_2) = r_1 r_2 (1 - x / r_1)(1 - x / r_2).\]

With a little algebra, we find that

\[\nonumber R(x) = \dfrac{x}{(1 - \alpha_1 x)(1 - \alpha_2 x)}\]

where

\[\begin{aligned} \alpha_1 &= \dfrac{1 + \sqrt{5}}{2} \\ \alpha_2 &= \dfrac{1 - \sqrt{5}}{2}. \end{aligned}\]

Next we find \(c_1\) and \(c_2\) which satisfy:

\[\label{15.3.1} \dfrac{x}{(1-\alpha_1 x)(1-\alpha_2 x)} = \dfrac{c_1}{1 - \alpha_1 x} + \dfrac{c_2}{1 - \alpha_2 x}\]

In general, we can do this by plugging in a couple of values for \(x\) to generate two linear equations in \(c_1\) and \(c_2\) and then solve the equations for \(c_1\) and \(c_2\). A simpler approach in this case comes from multiplying both sides of (\ref{15.3.1}) by the left hand denominator to get

\[\nonumber x = c_1 (1 - \alpha_2 x) + c_2 (1 - \alpha_1 x).\]

Now letting \(x = 1/\alpha_2\) we obtain

\[\nonumber c_2 = \dfrac{1/\alpha_2}{1 - \alpha_1 / \alpha_2} = \dfrac{1}{\alpha_2 - \alpha_1} = - \dfrac{1}{\sqrt{5}}.\]

and similarly, letting \(x = 1/\alpha_1\) we obtain

\[\nonumber c_1 = \dfrac{1}{\sqrt{5}}.\]

Plugging these values for \(c_1, c_2\) into equation (\ref{15.3.1}) finally gives the partial fraction expansion

\[\nonumber R(x) = \dfrac{x}{1 - x - x^2} = \dfrac{1}{\sqrt{5}} \left( \dfrac{1}{1 - \alpha_1 x} - \dfrac{1}{1 - \alpha_2 x} \right)\]

Each term in the partial fractions expansion has a simple power series given by the geometric sum formula:

\[\begin{aligned} \dfrac{1}{1 - \alpha_1 x} &= 1 + \alpha_1 x + \alpha_1 ^ 2 x^2 + \cdots \\ \dfrac{1}{1 - \alpha_2 x} &= 1 + \alpha_2 x + \alpha_2 ^ 2 x^2 + \cdots \end{aligned}\]

Substituting in these series gives a power series for the generating function:

\[\nonumber R(x) = \dfrac{1}{\sqrt{5}} ((1 + \alpha_1 x + \alpha_1 ^ 2 x^2 + \cdots) - (1 + \alpha_2 x + \alpha_2 ^ 2 x^2 + \cdots)),\]

so

\[\begin{align} \nonumber [x^n]R(x) &= \dfrac{\alpha_1 ^n - \alpha_2 ^n}{\sqrt{5}} \\ &= \dfrac{1}{\sqrt{5}}\left (\left( \dfrac{1 + \sqrt{5}}{2}\right)^n - \left( \dfrac{1 - \sqrt{5}}{2}\right)^n \right) \end{align}\]

Partial Fractions with Repeated Roots

Lemma 15.3.1 generalizes to the case when the denominator polynomial has a repeated nonzero root with multiplicity \(m\) by expanding the quotient into a sum a terms of the form

\[\nonumber \dfrac{c}{(1-\alpha x)^k}\]

where \(\alpha\) is the reciprocal of the root and \(k \leq m\). A formula for the coefficients of such a term follows from the donut formula (15.2.5).

\[[x^n]\left( \dfrac{c}{(1-\alpha x)^k}\right) = c\alpha ^n {n + (k-1) \choose n}.\]

When \(\alpha = 1\), this follows from the donut formula (15.2.5) and termwise multiplication by the constant \(c\). The case for arbitrary \(\alpha\) follows by substituting \(\alpha x\)for \(x\) in the power series; this changes \(x^n\) into \((\alpha x)^n\) and so has the effect of multiplying the coefficient of \(x^n\) by \(\alpha ^n\).²

²In other words,

\[\nonumber [x^n]F(\alpha x) = \alpha ^n \cdot [x^n]F(x).\]