7.3 Solving recurrence relations using generating functions

Generating functions of sequences

Definition and properties

A generating function encodes an entire sequence of numbers into a single algebraic expression. If you have a sequence $\{a_n\}$, its ordinary generating function (OGF) is the formal power series:

$G(x) = \sum_{n=0}^{\infty} a_n x^n = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots$

The key idea: the coefficient of $x^n$ in $G(x)$ is exactly $a_n$, the $n$th term of your sequence. This means all the information about the sequence lives inside one function.

A few things worth knowing upfront:

• Generating functions are treated as formal power series, meaning you don't always need to worry about whether the series converges. You're manipulating algebraic objects, not computing actual sums.
• The series can be finite or infinite depending on the sequence.
• Other types exist (exponential, Dirichlet), but for solving recurrence relations, ordinary generating functions are the standard tool.

Common examples

Building intuition with a few standard generating functions helps a lot:

• The constant sequence $a_n = 1$ gives $G(x) = \frac{1}{1-x}$, from the geometric series.
• The geometric sequence $a_n = r^n$ gives $G(x) = \frac{1}{1-rx}$.
• The sequence $a_n = n$ gives $G(x) = \frac{x}{(1-x)^2}$. You can derive this by differentiating $\frac{1}{1-x}$ and multiplying by $x$.
• More generally, $\frac{1}{(1-x)^k} = \sum_{n=0}^{\infty} \binom{n+k-1}{k-1} x^n$, which shows up constantly.

These building blocks reappear throughout the method, so recognizing them on sight saves time.

Deriving generating functions from recurrence relations

The core technique is to convert a recurrence relation into an algebraic equation for $G(x)$. Here's the general process:

Step-by-step process

1. Define the generating function. Let $G(x) = \sum_{n=0}^{\infty} a_n x^n$.

2. Multiply both sides of the recurrence by $x^n$ and sum over all valid values of $n$ (typically from the order of the recurrence to infinity).

3. Rewrite each sum in terms of $G(x)$ using shift properties. The most important ones:

   • $\sum_{n=1}^{\infty} a_{n-1} x^n = x \cdot G(x)$
   • $\sum_{n=2}^{\infty} a_{n-2} x^n = x^2 \cdot G(x)$
   • More generally, shifting by $k$ introduces a factor of $x^k$.

4. Incorporate initial conditions. When the summation range doesn't start at $n=0$, you'll need to peel off the first few terms and substitute the known initial values.

5. Solve the resulting algebraic equation for $G(x)$.

Worked example: Fibonacci sequence

The Fibonacci recurrence is $F_n = F_{n-1} + F_{n-2}$ with $F_0 = 0$, $F_1 = 1$.

1. Define $G(x) = \sum_{n=0}^{\infty} F_n x^n$.
2. Multiply the recurrence by $x^n$ and sum from $n=2$ to $\infty$:

$\sum_{n=2}^{\infty} F_n x^n = \sum_{n=2}^{\infty} F_{n-1} x^n + \sum_{n=2}^{\infty} F_{n-2} x^n$

1. Rewrite each side. The left side is $G(x) - F_0 - F_1 x = G(x) - x$. The right side is $x(G(x) - F_0) + x^2 G(x) = xG(x) + x^2 G(x)$.

2. So: $G(x) - x = xG(x) + x^2 G(x)$.

3. Solve for $G(x)$:

$G(x)(1 - x - x^2) = x \quad \Longrightarrow \quad G(x) = \frac{x}{1 - x - x^2}$

This is the generating function for the Fibonacci numbers. The next step is extracting a closed form from it.

Another example: $a_n = 3a_{n-1} - 2a_{n-2}$, $a_0 = 1$, $a_1 = 2$

Following the same steps, you'd arrive at:

$G(x) = \frac{1 - x}{1 - 3x + 2x^2}$

The denominator factors as $(1 - x)(1 - 2x)$, which sets up nicely for partial fractions.

Manipulating generating functions

Algebraic operations on generating functions

Once you have a generating function, algebraic operations on $G(x)$ correspond to specific operations on the underlying sequence:

• Addition/Subtraction: If $A(x)$ encodes $\{a_n\}$ and $B(x)$ encodes $\{b_n\}$, then $A(x) + B(x)$ encodes $\{a_n + b_n\}$. Term-by-term.
• Multiplication by $x^k$: Shifts the sequence by $k$ positions (prepends $k$ zeros).
• Multiplication of two generating functions: Produces the convolution of the two sequences. The coefficient of $x^n$ in $A(x) \cdot B(x)$ is $\sum_{k=0}^{n} a_k b_{n-k}$.
• Differentiation: $G'(x) = \sum_{n=1}^{\infty} n \cdot a_n x^{n-1}$, so $xG'(x) = \sum_{n=0}^{\infty} n \cdot a_n x^n$. Differentiation effectively multiplies the $n$th coefficient by $n$.
• Integration: $\int_0^x G(t)\,dt = \sum_{n=0}^{\infty} \frac{a_n}{n+1} x^{n+1}$, which divides each coefficient by $n+1$ and shifts the sequence.

Useful identities to recognize

• $\frac{1}{(1-x)^k} = \sum_{n=0}^{\infty} \binom{n+k-1}{k-1} x^n$
• $\frac{1}{\sqrt{1-4x}} = \sum_{n=0}^{\infty} \binom{2n}{n} x^n$ (the central binomial coefficients)
• The generating function for Catalan numbers: $C(x) = \frac{1 - \sqrt{1-4x}}{2x}$

Recognizing when your $G(x)$ matches one of these forms lets you read off the coefficients directly.

Extracting coefficients from generating functions

Getting $G(x)$ is only half the job. You still need to pull out $a_n$, the coefficient of $x^n$.

Methods for coefficient extraction

Direct expansion. If $G(x)$ is a known generating function (like $\frac{1}{(1-x)^k}$), you can read off the coefficients using the corresponding formula.

Partial fraction decomposition. This is the most common method for rational generating functions (where $G(x)$ is a ratio of polynomials). You decompose $G(x)$ into simpler fractions, each of which corresponds to a recognizable series. See the next section for details.

Binomial series expansion. For generating functions involving fractional or negative exponents, use the generalized binomial theorem:

$$$(1+x)^\alpha = \sum_{n=0}^{\infty} \binom{\alpha}{n} x^n$$

where $\binom{\alpha}{n} = \frac{\alpha(\alpha-1)\cdots(\alpha-n+1)}{n!}$.

For example, extracting the coefficient of $x^n$ from $\frac{1}{\sqrt{1-4x}} = (1-4x)^{-1/2}$ gives $\binom{2n}{n}$.

Taylor expansion. When other methods don't apply cleanly, you can compute derivatives: $a_n = \frac{G^{(n)}(0)}{n!}$. This is rarely practical for finding a general closed form, but it's useful for computing specific terms.

Partial fraction decomposition for recurrence relations

Partial fractions are the workhorse for extracting closed-form solutions from rational generating functions. If $G(x)$ is a ratio of polynomials and the degree of the numerator is less than the degree of the denominator, you can decompose it.

The method

1. Factor the denominator of $G(x)$ completely.
2. Write the partial fraction form. For distinct linear factors $(1 - r_i x)$, write:

$G(x) = \frac{A_1}{1 - r_1 x} + \frac{A_2}{1 - r_2 x} + \cdots$

1. Solve for the constants $A_1, A_2, \ldots$ by clearing denominators and comparing coefficients (or plugging in convenient values of $x$).

2. Expand each fraction as a geometric series: $\frac{A_i}{1 - r_i x} = \sum_{n=0}^{\infty} A_i r_i^n x^n$.

3. Read off the closed form: $a_n = A_1 r_1^n + A_2 r_2^n + \cdots$

4. Verify by checking the initial conditions and substituting back into the recurrence.

Special cases

• Repeated roots. If the denominator has a factor $(1 - rx)^m$, the decomposition includes terms $\frac{A_1}{1 - rx} + \frac{A_2}{(1 - rx)^2} + \cdots + \frac{A_m}{(1 - rx)^m}$. The expansion of $\frac{1}{(1-rx)^m}$ involves $\binom{n+m-1}{m-1} r^n$, so the closed form will include polynomial factors multiplied by $r^n$.
• Complex conjugate roots. These arise from irreducible quadratic factors. The resulting terms can be rewritten using trigonometric functions (sines and cosines with specific amplitudes and phases), though this is less common in introductory problems.

Worked example: $a_n = 5a_{n-1} - 6a_{n-2}$, $a_0 = 0$, $a_1 = 1$

1. Deriving the generating function (following the earlier process) gives:

$G(x) = \frac{x}{1 - 5x + 6x^2}$

1. Factor the denominator: $1 - 5x + 6x^2 = (1 - 2x)(1 - 3x)$.

2. Decompose:

$\frac{x}{(1-2x)(1-3x)} = \frac{A}{1-2x} + \frac{B}{1-3x}$

Clearing denominators: $x = A(1-3x) + B(1-2x)$.

Setting $x = \frac{1}{2}$: $\frac{1}{2} = A \cdot \frac{-1}{2}$, so $A = -1$.

Setting $x = \frac{1}{3}$: $\frac{1}{3} = B \cdot \frac{1}{3}$, so $B = 1$.

1. So $G(x) = \frac{-1}{1-2x} + \frac{1}{1-3x}$, and expanding:

$a_n = -2^n + 3^n = 3^n - 2^n$

1. Check: $a_0 = 1 - 1 = 0$ ✓, $a_1 = 3 - 2 = 1$ ✓, $a_2 = 9 - 4 = 5 = 5(1) - 6(0) = 5$ ✓.

This same approach works for any linear recurrence with constant coefficients, as long as you can factor the denominator. The generating function method and the characteristic equation method will always give the same answer, but generating functions generalize more easily to non-constant-coefficient and non-homogeneous recurrences.