Extracting Coefficients and Partial Fractions
You'll learn how to break down generating functions into simpler parts to find exact formulas for sequence terms.
The Core Idea
When you've built a generating function to solve a recurrence or counting problem, you often end up with a rational function (a fraction of polynomials). To extract the coefficient of x^n—which gives you the nth term of your sequence—you need an explicit formula, not just a compact fraction.
Partial fraction decomposition is your key tool. You split a complex fraction like:
3x + 2
---------------
(1 - 2x)(1 - 3x)
into simpler pieces:
A B
------ + ------
1 - 2x 1 - 3x
Each piece has a known power series expansion. For example, 1/(1-ax) = 1 + ax + a²x² + a³x³ + ..., so the coefficient of x^n is simply a^n.
Why This Matters
After decomposing, you recognize each fraction as a geometric series. The coefficient of x^n in A/(1-2x) is A·2^n, and in B/(1-3x) it's B·3^n. Add them together, and you have an explicit formula: the nth term equals A·2^n + B·3^n.
This transforms a recurrence relation's solution from an abstract generating function into a concrete, calculable formula you can evaluate for any n—like the Fibonacci formula you derived earlier.
Key Takeaway: Partial fraction decomposition converts rational generating functions into sums of simple fractions, each yielding a recognizable sequence whose coefficients give you an explicit formula for your original sequence.