Generating Functions

"A generating function is a clothesline on which we hang up a sequence of numbers for display." — Herbert Wilf. This tool transforms problems about sequences into problems about functions.

Definition

Definition (Ordinary Generating Function)

The ordinary generating function (OGF) for a sequence

a_{0}, a_{1}, a_{2}, \dots

is the formal power series:

A (x) = n = 0 \sum \infty a_{n} x^{n} = a_{0} + a_{1} x + a_{2} x^{2} + \dots

Common Series

Geometric Series: $\sum_{n = 0}^{\infty} x^{n} = \frac{1}{1 - x}$ (Sequence: $1, 1, 1, \dots$ )
Binomial Theorem: $(1 + x)^{n} = \sum_{k = 0}^{n} (k n) x^{k}$ .
Negative Binomial: $\frac{1}{( 1 - x ) ^{k}} = \sum_{n = 0}^{\infty} (k - 1 n + k - 1) x^{n}$ .

Applications

1. Solving Recurrences

To solve

a_{n} = 3 a_{n - 1} + 2

with

a_{0} = 0

Multiply by $x^{n}$ and sum over $n$ .
Express $A (x) = \sum a_{n} x^{n}$ in terms of itself.
Solve for $A (x)$ algebraically.
Expand $A (x)$ back into a series to find the coefficient $a_{n}$ .

2. Combinatorics (Partitions)

The number of ways to make change for

N

cents using coins of value

1, 5, 10

is the coefficient of

x^{N}

in:

A (x) = (\sum x^{i}) (\sum x^{5 j}) (\sum x^{10 k}) = \frac{1}{1 - x} \cdot \frac{1}{1 - x ^{5}} \cdot \frac{1}{1 - x ^{10}}

Snake Oil Method

A technique for evaluating combinatorial sums by treating them as coefficients in a product of generating functions.

Practice Problems

Exercise (Problem 1)

Find the generating function for the sequence

a_{n} = n

Exercise (Problem 2)

Find the closed form for the Fibonacci numbers

F_{n}

using the generating function

F (x) = \frac{x}{1 - x - x ^{2}}

Exercise (Problem 3)

Find the coefficient of

x^{5}

(1 + x + x^{2} + x^{3})^{4}