// Theory

Theory & Core Principles

02

// Worked Examples

Worked Examples

Step-by-step solutions showing how to apply the technique.

01

Worked Example 1: Solving the Fibonacci Recurrence

// Problem

Find a closed-form formula for the sequence defined by $a_0 = 0$, $a_1 = 1$, and $a_n = a_{n-1} + a_{n-2}$ for $n \ge 2$ using ordinary generating functions.

Key Idea

Multiplying the recurrence by $x^n$ and summing over all $n \ge 2$ transforms the recurrence into an algebraic equation for $A(x) = \sum_{n=0}^{\infty} a_n x^n$.

// Solution

1
Define the Generating Function: Let $A(x) = \sum_{n=0}^{\infty} a_n x^n = a_0 + a_1 x + a_2 x^2 + \dots = x + \sum_{n=2}^{\infty} a_n x^n$.
1
Apply the Recurrence: Substitute $a_n = a_{n-1} + a_{n-2}$ into the sum:

$$A(x) - x = \sum_{n=2}^{\infty} (a_{n-1} + a_{n-2})x^n = x \sum_{n=2}^{\infty} a_{n-1}x^{n-1} + x^2 \sum_{n=2}^{\infty} a_{n-2}x^{n-2}$$

$$A(x) - x = x A(x) + x^2 A(x)$$

1
Solve for $A(x)$:

$$A(x)(1 - x - x^2) = x \implies A(x) = \frac{x}{1 - x - x^2}$$

1
Partial Fraction Decomposition: Factoring $1 - x - x^2 = (1 - \phi x)(1 - \hat{\phi} x)$ where $\phi = \frac{1+\sqrt{5}}{2}$ and $\hat{\phi} = \frac{1-\sqrt{5}}{2}$:

$$A(x) = \frac{1}{\sqrt{5}}\left(\frac{1}{1 - \phi x} - \frac{1}{1 - \hat{\phi} x}\right) = \frac{1}{\sqrt{5}} \sum_{n=0}^{\infty} (\phi^n - \hat{\phi}^n) x^n$$

1
Conclusion: Extracting the coefficient of $x^n$ yields Binet's formula: $a_n = \frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right)$.

02

Worked Example 2: Integer Partitions into Coins

// Problem

Find the number of ways to make change for $n$ cents using pennies ($1¢$), nickels ($5¢$), and dimes ($10¢$).

Key Idea

Each coin denomination contributes a factor of the geometric series $(1 + x^k + x^{2k} + \dots) = \frac{1}{1 - x^k}$ to the product generating function.

// Solution

1
Construct Individual Generating Functions:

■
Pennies ($1¢$): $1 + x^1 + x^2 + x^3 + \dots = \frac{1}{1 - x}$
■
Nickels ($5¢$): $1 + x^5 + x^{10} + x^{15} + \dots = \frac{1}{1 - x^5}$
■
Dimes ($10¢$): $1 + x^{10} + x^{20} + x^{30} + \dots = \frac{1}{1 - x^{10}}$

1
Form the Product Generating Function: The number of ways to form $n$ cents is $[x^n] F(x)$, where:

$$F(x) = \frac{1}{(1 - x)(1 - x^5)(1 - x^{10})}$$

1
Interpret the Expansion: Multiplying the polynomial series computes every combination $x^{1\cdot a} \cdot x^{5\cdot b} \cdot x^{10\cdot c} = x^{a + 5b + 10c}$.
1
Conclusion: The number of non-negative integer solutions to $a + 5b + 10c = n$ is precisely the coefficient of $x^n$ in the Maclaurin expansion of $F(x) = \frac{1}{(1 - x)(1 - x^5)(1 - x^{10})}$.

03

Worked Example 3: Deriving the Closed Form for Catalan Numbers

// Problem

The Catalan numbers satisfy $C_0 = 1$ and $C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i}$ for $n \ge 1$. Find the ordinary generating function $C(x)$ and determine $C_n$.

Key Idea

The convolution in the recurrence corresponds directly to squaring the generating function: $C(x)^2$.

// Solution

1
Set Up the Algebraic Relation: Let $C(x) = \sum_{n=0}^{\infty} C_n x^n$. Multiplying both sides of the recurrence by $x^n$ and summing for $n \ge 1$:

$$C(x) - C_0 = x \sum_{n=1}^{\infty} \left(\sum_{i=0}^{n-1} C_i C_{n-1-i}\right) x^{n-1} = x C(x)^2$$

$$x C(x)^2 - C(x) + 1 = 0$$

1
Solve the Quadratic Equation: Using the quadratic formula:

$$C(x) = \frac{1 \pm \sqrt{1 - 4x}}{2x}$$

Since $C(0) = C_0 = 1$, we must choose the minus sign to avoid division by zero: $C(x) = \frac{1 - \sqrt{1 - 4x}}{2x}$.

1
Binomial Series Expansion: Expanding $\sqrt{1 - 4x} = (1 - 4x)^{1/2}$ via generalized binomial theorem:

$$(1 - 4x)^{1/2} = 1 - \sum_{n=1}^{\infty} \frac{1}{2n-1}\binom{2n}{n} x^n \frac{1}{2^{2n-1}} \cdot 4^n = 1 - 2\sum_{n=1}^{\infty} \frac{1}{n}\binom{2n-2}{n-1} x^n$$

1
Conclusion: Substituting back into $C(x)$ and shifting indices yields $C_n = \frac{1}{n+1}\binom{2n}{n}$.

03

// Practice

Practice Problems

Try solving these problems on your own before checking the hints or solution.

01

Practice Challenge 1: Number of Non-Negative Integer Solutions

Introductory Level

// Problem

Find the number of integer solutions to $x_1 + x_2 + x_3 + x_4 = 20$ such that $1 \le x_1 \le 5$, $x_2 \ge 0$, $x_3 \ge 2$, and $x_4 \in \{0, 1, 2, 3\}$ using generating functions.

// Hints

02

Practice Challenge 2: Derangements via Exponential Generating Functions

Advanced Level

// Problem

A derangement $D_n$ is a permutation of $n$ elements with no fixed points. Using exponential generating functions (EGF), find the closed-form expression for the EGF $D(x) = \sum_{n=0}^{\infty} D_n \frac{x^n}{n!}$ and extract the formula for $D_n$.

// Hints