Generating Functions

Pack a sequence into one power series — the geometric series does the work.

The idea

A generating function encodes an entire sequence as a single power series, so that we can operate on the sequence with ordinary algebra.

Definition (Ordinary generating function).

The ordinary generating function of a sequence $a_{0}, a_{1}, a_{2}, \dots$ is the formal power series $A(x) = \sum_{n \ge 0} a_{n} x^{n} = a_{0} + a_{1} x + a_{2} x^{2} + \cdots.$

The power $x^{n}$ is a position marker: it records that $a_{n}$ is the $n$th term and keeps it distinct from its neighbours. We never substitute a number for $x$ and never sum the series numerically, so convergence does not arise — the series is a formal object. The notation $[x^{n}] A(x)$, read as the coefficient of $x^{n}$ in $A$, denotes $a_{n}$ and recovers the sequence from the series.

The sequence and its generating function carry exactly the same information. The gain is that ordinary algebra on $A(x)$ mirrors operations on the sequence, and an infinite series often collapses to a short closed form from which the whole sequence can be read off.

Ways to work on it

• Walkthrough. The ordinary generating function, the geometric series 1/1-x, and reading off a coefficient.
• Practice. Extract a coefficient of 1/1-cx, or close ∑ (cx)^n into a fraction.
• Hardest. Find the generating function of a geometric sequence, then extract a coefficient from it.

Not sure where to start? Take the ten-question placement test.