Course contentsShow
← Mathematics
Lesson 2645 of 3,12152. CombinatoricsFree lesson

Extracting Coefficients and Partial Fractions

Use partial fraction decomposition to extract explicit formulas for sequence terms from generating functions.

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.