Generating Functions

Pack a whole sequence into one function the way a zip file packs folders: algebra on the package does counting for every entry at once.

One rational function x over 1 minus x minus x squared expands into the whole Fibonacci sequence 0 1 1 2 3 5, one coefficient per term

Why Does This Exist?

Counting problems ask about whole sequences at once: how many binary strings of length $n$ avoid consecutive ones, for every $n$ ? Answering term by term means solving infinitely many problems. A generating function folds the entire sequence into a single object

G(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots

and then ordinary algebra on $G$ answers questions about all the $a_n$ simultaneously. A recurrence between sequence terms becomes an equation for $G$ ; solving that equation and reading off coefficients solves the recurrence in closed form.

The same idea resurfaces wherever series do work: moment generating functions in probability package a distribution's moments the same way, and Taylor series are generating functions for a smooth function's derivatives. Learn the trick once here and both of those read as dialects.

The one idea you need first

A power series is a polynomial that never ends: coefficients $a_n$ attached to increasing powers of $x$ . Two series are equal exactly when all their coefficients match, so extracting information means reading coefficients. Adding series adds coefficients term by term; multiplying convolves them, which is why products of generating functions count combined choices.

Think of It Like This

A zip archive for sequences

A folder of a thousand text files is awkward to email, so you zip it into one archive. The archive is not the files, but every file is recoverable from it, and some operations (copying, checksumming) are easier on the single package.

A generating function is a zip archive for a sequence. The "files" are the terms $a_0, a_1, a_2, \ldots$ and the "archive" is the function $G(x)$ . Adding archives merges file lists term by term. Differentiating shifts and reweights the contents. And just as you would never edit a photo by hex-editing its zip, you manipulate the sequence through the function, then unzip by reading coefficients at the end.

The analogy stops at convergence: a zip always opens, but a power series only represents its sequence where it converges, and formal manipulation outside that range can lie.

How It Actually Works

Start from a recurrence and let the series do the bookkeeping. The Fibonacci numbers $F_0 = 0$ , $F_1 = 1$ , $F_n = F_{n-1} + F_{n-2}$ have generating function $F(x) = \sum_{n \ge 0} F_n x^n$ . Multiply the recurrence by $x^n$ and sum over $n \ge 2$ :

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

The left side is $F(x) - x$ (missing only the $n = 1$ term $x$ ). The first sum on the right is $x F(x)$ and the second is $x^2 F(x)$ . So $F(x) - x = xF(x) + x^2 F(x)$ , giving the closed package:

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

Worked example

Expand the package by long division and watch the sequence emerge. Write $(1 - x - x^2)(a_0 + a_1 x + a_2 x^2 + a_3 x^3 + a_4 x^4 + a_5 x^5) = x$ and match coefficients:

constant: $a_0 = 0$
$x$ : $a_1 - a_0 = 1$ , so $a_1 = 1$
$x^2$ : $a_2 - a_1 - a_0 = 0$ , so $a_2 = 1$
$x^3$ : $a_3 - a_2 - a_1 = 0$ , so $a_3 = 2$
$x^4$ : $a_4 - a_3 - a_2 = 0$ , so $a_4 = 3$
$x^5$ : $a_5 - a_4 - a_3 = 0$ , so $a_5 = 5$

Out comes $0, 1, 1, 2, 3, 5$ : Fibonacci, recovered from one rational function with no guessing. From here partial fractions lead to Binet's closed form, but the coefficient extraction above is already the whole method.

Code

The point is the check: rebuild the coefficients from the recurrence the algebra implies, and confirm they match.

1def fib_from_package(n_terms: int) -> list[int]:2    a = [0] * n_terms3    for n in range(n_terms):4        if n == 1:5            a[n] = 1  # the lone x on the right hand side6        elif n >= 2:7            a[n] = a[n - 1] + a[n - 2]  # coefficient matching rule8    return a9
10
11print(fib_from_package(6))  # -> [0, 1, 1, 2, 3, 5]

Watch Out For

Mixing up ordinary and exponential generating functions

Ordinary generating functions attach $a_n$ to $x^n$ ; exponential ones attach $a_n$ to $x^n / n!$ . The two packages answer different questions (unlabelled versus labelled structures) and their product rules differ. Using ordinary multiplication on exponential packages scrambles the counts. Check which convention your source uses before combining anything.

Manipulating where the series diverges

Formal algebra on $G(x)$ is valid inside its radius of convergence; outside it, rearranging terms can produce any answer you like. When extracting asymptotics or evaluating at a point, confirm the point lies inside the disc first. The zip analogy breaks exactly here: every zip opens, but not every series converges.

The Quick Version

A generating function packs a whole sequence into one power series: $G(x) = a_0 + a_1 x + \cdots$ .
Recurrences between terms become solvable equations for the package function.
Fibonacci falls out of $x / (1 - x - x^2)$ : matching coefficients gives 0, 1, 1, 2, 3, 5.
Ordinary and exponential variants answer different counting questions; do not mix them.
Series algebra is only trustworthy inside the radius of convergence.