Generating functions: a clothesline for numbers

This is a sample article. Replace it with your own writing — it exists so you can see the math voice (same chalkboard, bluer chalk) and code on dark.

Herbert Wilf described a generating function as "a clothesline on which we hang up a sequence of numbers for display." The definition looks almost too simple to be useful: given a sequence $a_0, a_1, a_2, \ldots$, form the formal power series

The $x$ is not a number and we never plug anything into it. It is a bookkeeping device: the coefficient of $x^n$ is the $n$-th term. The payoff is that operations on sequences — shifting, summing, convolving — become ordinary algebra on $A(x)$.

Fibonacci, mechanically

Take $F_0 = 0$, $F_1 = 1$, $F_{n} = F_{n-1} + F_{n-2}$, and let $F(x) = \sum_n F_n x^n$. Multiply the recurrence by $x^n$ and sum over $n \ge 2$. Each shifted sum is $F(x)$ times a power of $x$, and after collecting terms:

The entire infinite sequence, packed into one rational function. Now partial fractions: the denominator factors using the golden ratio $\varphi = (1+\sqrt5)/2$ and its conjugate $\psi = (1-\sqrt5)/2$, each factor expands as a geometric series, and reading off the coefficient of $x^n$ gives Binet's formula,

without a single clever guess. The recurrence went in; algebra happened; the closed form fell out. That is the generating-function method in one sentence: recurrences become algebra, and coefficient extraction becomes the only hard step.

Checking ourselves

Formal power series are also pleasantly checkable. Expand the rational function numerically and compare against the recurrence:

from fractions import Fraction
 
def series_coeffs(num, den, n):
    """Coefficients of num/den as a power series, via long division."""
    num, den = list(map(Fraction, num)), list(map(Fraction, den))
    out = []
    for _ in range(n):
        c = num[0] / den[0]
        out.append(c)
        # subtract c * den from num, then shift
        num = [a - c * b for a, b in zip(num + [0] * len(den), den + [0] * len(num))]
        num = num[1:] or [Fraction(0)]
    return out
 
# x / (1 - x - x^2)
print(series_coeffs([0, 1], [1, -1, -1], 10))
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

The clothesline holds.

Why this matters beyond Fibonacci

Any linear recurrence with constant coefficients yields a rational generating function the same way, which is why they all have Binet-style closed forms. Products of generating functions compute convolutions, which is why they dominate counting problems: the coefficient of $x^n$ in $(1 + x + x^2 + \cdots)^k$ counts the ways to write $n$ as an ordered sum of $k$ non-negative integers, and you have derived stars-and-bars by multiplying series. Once you start seeing counting problems as coefficient extractions, it is hard to stop.