Solving Recurrences with OGFs

In our previous lesson, we embarked on a new way of thinking about sequences by encoding them into single algebraic objects called ordinary generating functions (OGFs). We focused exclusively on the construction of these functions, translating the rules of a combinatorial problem into a rational function $G (x)$ . The tantalizing question we left unanswered was how to reverse this process: given a compact function like $G (x) = \frac{1}{1 - x - x ^{2}}$ , how do we extract the $n$ -th term of the sequence it represents?

Today, we will answer that question. You will learn the complete, powerful method of using generating functions to find closed-form solutions for linear recurrence relations. The central technique that unlocks this process is partial fraction decomposition, an algebraic tool that allows us to break down complex rational functions into simpler pieces whose series expansions we already know. By the end of this lesson, you will be able to solve a recurrence relation from start to finish using this elegant methodology.

The "Generatingfunctionology" Method

Solving a linear recurrence relation with generating functions follows a systematic, five-step process. Let's say we have a sequence $(a_{n})$ defined by a recurrence and some initial values.

Define: Write down the generating function for the sequence, $G (x) = \sum_{n = 0}^{\infty} a_{n} x^{n}$ .
Transform: Multiply the entire recurrence relation by $x^{n}$ and sum from the first value of $n$ for which the recurrence is valid. Manipulate the resulting summations to express them in terms of $G (x)$ and the initial values.
Solve: Solve the resulting algebraic equation to find a closed-form expression for $G (x)$ , which will typically be a rational function (a ratio of polynomials).
Decompose: Use partial fraction decomposition to break $G (x)$ into a sum of simpler fractions.
Extract: Recognize each simple fraction as the generating function for a known sequence (usually a geometric progression) and add their explicit formulas to find the closed-form expression for $a_{n}$ .

Let's walk through this process.

Step 1: From Recurrence to a Rational Function

The first major step is to convert the recurrence relation into an equation that involves its generating function, $G (x)$ . The key is to see how terms like $a_{n - 1}$ and $a_{n - 2}$ relate to $G (x)$ .

$\sum_{n = 1}^{\infty} a_{n - 1} x^{n} = x \sum_{n = 1}^{\infty} a_{n - 1} x^{n - 1} = x \sum_{k = 0}^{\infty} a_{k} x^{k} = x G (x)$
$\sum_{n = 2}^{\infty} a_{n - 2} x^{n} = x^{2} \sum_{n = 2}^{\infty} a_{n - 2} x^{n - 2} = x^{2} \sum_{k = 0}^{\infty} a_{k} x^{k} = x^{2} G (x)$

This technique of shifting the index of summation is fundamental. The following reading shows how this is applied to a second-order recurrence.

CTGD Generating Functions and Recurrence Relations

This section from Kenneth Bogart's online textbook demonstrates the first crucial step: converting a second-order linear recurrence relation into an algebraic equation for its generating function.

Please read the setup in Problem 213. Pay close attention to how the recurrence a_n=a_{n-1} + 2a_{n-2} is algebraically manipulated, along with the initial condition, to isolate the generating function G(x) and arrive at the expression G(x) = \frac{10}{1-x-2x^2}.

Steps 2-5: Decomposition and Extraction

Once we have $G (x)$ as a rational function, we need to break it apart. This is where partial fractions come in. The goal is to rewrite a complicated fraction as a sum of simpler ones, like $\frac{A}{1 - r _{1} x} + \frac{B}{1 - r _{2} x}$ , because we know that $\frac{1}{1 - r x}$ generates the sequence $r^{0}, r^{1}, r^{2}, \dots$ .

The following reading introduces the algebra behind this decomposition.

CTGD Generating Functions and Recurrence Relations

This next section introduces the algebraic technique needed to break down our generating function into manageable pieces.

Read the subsection "Partial fractions", up to the end of the paragraph before Problem 219. This explains the logic of finding the unknown coefficients (like c and d) by creating and solving a system of linear equations.

An end-to-end video example will cement the entire process. The following video solves a complete problem from start to finish, showing how all the pieces fit together.

RECURRENCE RELATIONS using GENERATING FUNCTIONS - DISCRETE MATHEMATICS

Let's watch a complete, end-to-end example. This video from TrevTutor solves the recurrence a_n = 5a_{n-1} - 4a_{n-2} using the exact method we are learning.

Watch the entire video. Pay special attention to these parts: Setting up G(x): This reinforces the first step we just read about. Partial Fractions: This is the core of the process. Notice the method used to find the values of A and B. Finding the Solution: This shows how to convert the simple fractions back into sequences and combine them to get the closed form for a_n.

Handling Repeated Roots

The examples so far have denominators with distinct linear factors, like $(1 - x) (1 - 2 x)$ . But what if the denominator has a repeated factor, such as $(1 - 3 x)^{2}$ ? The partial fraction setup changes slightly. A term $(1 - r x)^{k}$ in the denominator requires $k$ separate terms in the decomposition:
$\frac{A _{1}}{1 - r x} + \frac{A _{2}}{( 1 - r x ) ^{2}} + \dots + \frac{A _{k}}{( 1 - r x ) ^{k}}$
To find the sequence for a term like $\frac{1}{( 1 - a x ) ^{k}}$ , we use the generalized binomial theorem, which gives the identity:
$\frac{1}{( 1 - z ) ^{k}} = \sum_{n = 0}^{\infty} (k - 1 n + k - 1) z^{n}$
So, the coefficient of $x^{n}$ in $\frac{1}{( 1 - a x ) ^{k}}$ is $(k - 1 n + k - 1) a^{n}$ . For $k = 2$ , this simplifies to $(n + 1) a^{n}$ .

The next video tackles a problem with a repeated root. While the recurrence is non-homogeneous (it has an extra term that doesn't depend on previous $a_{i}$ ), the algebraic process for setting up and solving the partial fraction decomposition is exactly what we need to see.

Discrete Math II - 8.4.7 Solve Recurrence Relations with Generating Functions

This video from Kimberly Brehm tackles a more complex problem that involves a repeated root in the denominator of the generating function.

First, observe the generating function derived at this point. Notice its denominator contains (1-x)^2(1-3x). See how this repeated root changes the partial fraction decomposition at this step, requiring terms for both (1-x) and (1-x)^2. You can then watch the detailed algebraic work of solving for the coefficients A, B, and C from this point. Focus on understanding the process of setting up and solving the system of equations.

Practice Problems

Now it's your turn to apply the full method. For each problem, use generating functions and partial fractions to find the closed-form formula for $a_{n}$ .

The Fibonacci Sequence: Find the explicit formula for the $n$ -th Fibonacci number, defined by $F_{n} = F_{n - 1} + F_{n - 2}$ for $n \geq 2$ , with initial conditions $F_{0} = 0$ and $F_{1} = 1$ . This is a classic application and will result in the famous Binet's formula.
Solve the recurrence relation $a_{n} = 6 a_{n - 1} - 9 a_{n - 2}$ for $n \geq 2$ , with initial conditions $a_{0} = 1$ and $a_{1} = 6$ . (Hint: Be mindful of the denominator you get for $G (x)$ ).
Solve the recurrence relation $a_{n} = 2 a_{n - 1} + 3 n - 1$ for $n \geq 1$ , with $a_{0} = 1$ . This is a non-homogeneous recurrence. When you transform it, you will get an extra term from the sum of $(3 n - 1) x^{n}$ . Use the identities from our previous lessons to find the generating functions for the sequences $(3 n)$ and $(- 1)$ .

Conclusion

Today, you have learned one of the most elegant and powerful techniques in combinatorics: solving linear recurrence relations using generating functions. We've seen how a problem that starts with a discrete sequence can be translated into the continuous world of algebra, solved using tools like partial fraction decomposition, and then translated back to find a precise, closed-form solution. You now have the full "generatingfunctionology" pipeline at your disposal.

In our next lesson, we will continue exploring generating functions by tackling a famous combinatorial sequence: the Catalan numbers. You will learn how some problems, which at first seem unrelated, all lead to the same recurrence relation and the same sequence of numbers, and we will derive the generating function that unifies them all.