Section 8.1 Partial fractions
If a generating function looks like 1/(1+axi)j, we can use the Generalised Binomial Theorem to find the coefficient of xr. But what can we do if the generating function looks like 1/(a+bx+cx2), for example, or some even more complicated expression? One tool that can help us extract coefficients from some expressions like this, is the method of partial fractions.Example 8.1.1.
Suppose we have a generating function
How can we work out the coefficient of \(x^r\text{?}\)
Well, if we could separate the factors of the denominator, we would know how to deal with each separately. In fact, this is exactly what we do. We set
As we work this through, you'll see that in working this out, we end up with two equations in the two unknowns \(A\) and \(B\text{,}\) which we can therefore solve! So it is possible to βsplit upβ the original generating function, into two separate fractions, each of which has as its denominator one of the factors of the original denominator. This is the method of partial fractions.
To solve for \(A\) and \(B\text{,}\) we add the fractions \(A/(1-2x)\) and \(B/(2+x)\) over a common denominator. This gives
Clearly, this forces the numerators to be equal, so
Since these are equal as polynomials in \(x\text{,}\) the constant terms must be equal, and the coefficients of \(x\) must be equal, giving us two equations: \(2A+B=1\) and \((A-2B)x=x\text{,}\) so \(A-2B=1\text{.}\) Now there are many ways to algebraically solve for \(A\) and \(B\text{;}\) for example, the first equation gives \(B=1-2A\text{;}\) plugging this into the last equation gives \(A-2(1-2A)=1\text{,}\) so \(5A=3\text{,}\) so \(A=3/5\text{.}\) Now
Thus, we have
Notice that the \(2+x\) is still a bit problematic. We can use the Generalised Binomial Theorem to work out coefficients for something that looks like \((1+ax^i)^j\text{,}\) but we need that \(1\text{,}\) and here instead we have a \(2\text{.}\) To deal with this, we observe that
Thus,
Now let's expand each of the two summands separately. We have
so the coefficient of \(x^r\) in this part is \((3/5)2^r\text{.}\) Also,
so the coefficient of \(x^r\) in this part is \((-1/10)(-1)^r(1/2)^r\text{.}\)
Thus, the coefficient of \(x^r\) in \(f(x)\) is \((3/5)2^r-1/10(-1/2)^r\text{.}\)
Exercises 8.1.2.
Find the coefficient of \(x^r\) in each of the following generating functions, using the method of partial fractions and the Generalised Binomial Theorem.
\(\displaystyle \frac{1}{(1+2x)(2-x)}\)
\(\displaystyle \frac{x}{(1+x)^2(1-x)}\)
\(\displaystyle \frac{1+2x}{(1-2x)(2+x)(1+x)}\)