1. What a generating function is
Start with the simplest infinite sequence imaginable: $(1, 1, 1, 1, \ldots)$ — a one at every position, forever. Hang each term off a power of $x$ and add them up:
$$ 1 + x + x^2 + x^3 + x^4 + \cdots $$By the geometric-series identity, that whole infinite sum collapses to
$$ \frac{1}{1 - x}. $$Pause on that. An infinite sequence — endless in principle, awkward to store, awkward to manipulate — has just been folded into three symbols. The list is still in there: if you ever want $a_5$, you crank out the power series of $1/(1-x)$ and read off the coefficient of $x^5$. The bookkeeping is lossless. And now you can do algebra on the sequence by doing algebra on the closed form. That trick — encode, manipulate, decode — is the whole game.
The general object behind it has a name:
For a sequence $a_0, a_1, a_2, \ldots$, the ordinary generating function is the formal power series
$$ A(x) = \sum_{n=0}^{\infty} a_n x^n = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots $$The sequence is recovered by reading off coefficients: $a_n = [x^n]\, A(x)$.
One piece of fine print about what we just did. The $x$ in $1 + x + x^2 + \cdots = 1/(1-x)$ is not a number you plug in — if it were, you'd worry that the sum diverges for $|x| \ge 1$ and refuse to write the equality at all. A generating function is a formal power series: a bookkeeping device whose coefficients carry the meaning. We will add and multiply these series the way we add and multiply polynomials, and never ask whether they converge for any particular $x$. Convergence becomes relevant only when we want to plug in a real value or extract asymptotics; for counting, it doesn't.
$[x^n]A(x)$ means "the coefficient of $x^n$ in $A(x)$." It is the inverse of the encoding: $[x^n]\bigl(\sum a_k x^k\bigr) = a_n$. Most generating-function calculations boil down to manipulating $A(x)$ algebraically and then extracting $[x^n]$ at the end.
2. Why algebra on $A(x)$ is combinatorics on $(a_n)$
The reason generating functions work is a single fact about how power series multiply. If
$$ A(x) = \sum_{n \ge 0} a_n x^n, \qquad B(x) = \sum_{n \ge 0} b_n x^n, $$then the coefficient of $x^n$ in $A(x)B(x)$ is
$$ [x^n]\, A(x)B(x) = \sum_{k=0}^{n} a_k\, b_{n-k}. $$That sum is the convolution of the two sequences. It is also — and this is the combinatorial punchline — the number of ways to choose some amount $k$ of one thing and the rest $n - k$ of another, summed over all valid splits.
Read the correspondence as a dictionary:
| Operation on $A(x)$ | Effect on $(a_n)$ | Combinatorial reading |
|---|---|---|
| $A(x) + B(x)$ | $a_n + b_n$ | Disjoint union of two ways to build the same object |
| $A(x) \cdot B(x)$ | $\sum_{k} a_k b_{n-k}$ | Build an object of "size" $n$ by combining one piece of size $k$ with another of size $n-k$ |
| $x A(x)$ | Shift right: $0, a_0, a_1, \ldots$ | Prepend an "empty slot" of size 1 |
| $A'(x)$ | $(n+1)a_{n+1}$ | Mark one of $n+1$ positions |
| $1/(1 - A(x))$ | Sequences of $A$-pieces | Build any-length list of $A$-things |
That dictionary is the whole game. Every counting problem you encode as a generating function will get translated through one of these rows.
If you want to count "ways to assemble something from a part of type $A$ plus a part of type $B$ where the total size is $n$," you are asking for the coefficient of $x^n$ in $A(x) \cdot B(x)$. That single observation drives the change-counting problem, the partition-counting problem, the Catalan numbers, and a great deal more.
3. The four identities you actually use
You will use thousands of generating-function manipulations in your life, and they will all be variations on these four. Commit them to memory; everything else follows.
The geometric series
$$ \frac{1}{1 - x} \;=\; \sum_{n=0}^{\infty} x^n \;=\; 1 + x + x^2 + x^3 + \cdots $$This is the OGF of the all-ones sequence $(1, 1, 1, \ldots)$. It is the master identity — every other identity here is derived from it.
The $k$-fold geometric series
$$ \frac{1}{(1 - x)^k} \;=\; \sum_{n=0}^{\infty} \binom{n + k - 1}{k - 1} x^n. $$The coefficient counts multisets of size $n$ drawn from a $k$-element alphabet, also known as the number of ways to place $n$ indistinguishable balls into $k$ distinguishable boxes. The connection to stars and bars is no accident — we'll see why in §4.
The binomial theorem
$$ (1 + x)^n \;=\; \sum_{k=0}^{n} \binom{n}{k} x^k. $$A finite polynomial, but it is a generating function nonetheless: it encodes row $n$ of Pascal's triangle. Multiplying $(1+x)^a$ by $(1+x)^b$ and reading off coefficients of $x^k$ gives the Vandermonde identity $\binom{a+b}{k} = \sum_j \binom{a}{j}\binom{b}{k-j}$ — convolution doing its job.
Scaled geometric
$$ \frac{1}{1 - ax} \;=\; \sum_{n=0}^{\infty} a^n x^n. $$The OGF of a geometric sequence with ratio $a$. This is the workhorse of partial fractions: any rational function $A(x) = P(x)/Q(x)$ can be decomposed into a sum of terms of this form (or its powers), and once it is, the coefficients are immediately readable.
Differentiate $1/(1-x) = \sum x^n$ once with respect to $x$. You get $1/(1-x)^2 = \sum n x^{n-1} = \sum (n+1) x^n$, which is the $k=2$ case of identity #2 with $\binom{n+1}{1} = n+1$. Differentiating $k-1$ more times (and dividing by $(k-1)!$) gives the full identity. No memorization required — just notice the pattern of "differentiate, get a factorial out front."
4. Stars and bars, revisited
You already know that the number of ways to place $n$ identical balls into $k$ distinguishable boxes is $\binom{n + k - 1}{k - 1}$. The combinatorial argument (stars and bars) is clever but ad hoc. Generating functions give the same answer mechanically, and the mechanics generalize where stars and bars cannot.
For a single box, the number of balls placed in it can be $0, 1, 2, \ldots$ — every nonnegative integer. Encode "this box receives $j$ balls" as the term $x^j$. The generating function for a single box is then
$$ 1 + x + x^2 + x^3 + \cdots \;=\; \frac{1}{1 - x}. $$With $k$ boxes, each filled independently, multiply $k$ copies of this generating function together. By the convolution rule, the coefficient of $x^n$ in the product is precisely the number of ways to split $n$ into $k$ ordered nonnegative summands:
$$ \left( \frac{1}{1 - x} \right)^{\!k} \;=\; \frac{1}{(1 - x)^k} \;=\; \sum_{n \ge 0} \binom{n + k - 1}{k - 1} x^n. $$The coefficient $\binom{n + k - 1}{k - 1}$ is the stars-and-bars answer. We didn't have to invent a clever bijection — multiplication of generating functions was the bijection.
Suppose each box has its own restriction: box 1 must hold an even number of balls; box 2 must hold between 2 and 5 balls. Just change the per-box generating function — $1 + x^2 + x^4 + \cdots = 1/(1-x^2)$ for the first, $x^2 + x^3 + x^4 + x^5$ for the second — and multiply. The answer is the coefficient of $x^n$ in the product. Stars and bars cannot handle that, but generating functions absorb it without a flinch.
5. Making change for $n$ cents
Classic problem: how many ways can you make $n$ cents using pennies, nickels, dimes, and quarters? Pure combinatorics gets messy fast — generating functions barely break a sweat.
For each coin, the "amount of money contributed" can be 0¢, $d$¢, $2d$¢, $3d$¢, $\ldots$ where $d$ is the coin's denomination. So a coin worth $d$ has generating function
$$ 1 + x^d + x^{2d} + x^{3d} + \cdots \;=\; \frac{1}{1 - x^d}. $$Using any number of pennies, nickels, dimes, and quarters independently gives the product
$$ C(x) \;=\; \frac{1}{1 - x} \cdot \frac{1}{1 - x^5} \cdot \frac{1}{1 - x^{10}} \cdot \frac{1}{1 - x^{25}}. $$The number of ways to make $n$ cents is $[x^n]\, C(x)$. That is the whole solution. Expanding the product (by computer if $n$ is large) gives the count for every $n$ at once — for $n = 0, 5, 10, 15, 20, 25, 50, 100$ you get $1, 2, 4, 6, 9, 13, 49, 242$.
| Amount | Ways | Quick sanity check |
|---|---|---|
| 5¢ | 2 | 5 pennies; or 1 nickel |
| 10¢ | 4 | 10p; 5p+1n; 2n; 1d |
| 25¢ | 13 | all-penny; mixes of nickels/dimes; 1 quarter; … |
| $1.00 | 242 | (no fast hand check — that's the point) |
Want to count ways using coins of any denominations $d_1, d_2, \ldots, d_k$? The generating function is $\prod_i 1/(1 - x^{d_i})$. Want to require at least one quarter? Strip the leading $1$ from that factor: $x^{25}/(1 - x^{25})$. Want at most two quarters? Use $1 + x^{25} + x^{50}$. The combinatorics is whatever you decide to multiply.
6. Solving linear recurrences
The other headline use is solving recurrences in closed form. The recipe is mechanical and the same every time:
- Define $A(x) = \sum_{n \ge 0} a_n x^n$.
- Multiply the recurrence by $x^n$ and sum over all $n$ for which it holds.
- Recognize the resulting sums as shifted copies of $A(x)$ and solve for $A(x)$ as a rational function $P(x)/Q(x)$.
- Decompose $A(x)$ into partial fractions.
- Extract $[x^n]$ using the scaled-geometric identity.
Each step is a routine application of an identity from §3. The only ingenuity is at step 4, and it is the same ingenuity you used in calculus to integrate rational functions.
After step 3 you have $A(x) = P(x)/Q(x)$, a rational function. Factor $Q(x) = \prod_i (1 - r_i x)$ — then partial fractions writes $A$ as a sum of terms $\frac{c_i}{1 - r_i x}$. By identity #4, each such term contributes $c_i r_i^n$ to the coefficient of $x^n$. So $a_n$ is a linear combination of $n$-th powers of the roots' reciprocals. That is the structure of every solution to a linear recurrence with constant coefficients.
7. Worked derivation: Fibonacci to Binet
Take the Fibonacci recurrence with its usual initial conditions:
$$ F_0 = 0, \quad F_1 = 1, \quad F_n = F_{n-1} + F_{n-2} \text{ for } n \ge 2. $$We will derive Binet's closed form by following the recipe. The point is not the answer — you have probably seen it — but to watch generating functions do all the work.
Step 1: Define $F(x)$
$$ F(x) \;=\; \sum_{n \ge 0} F_n x^n \;=\; F_0 + F_1 x + F_2 x^2 + F_3 x^3 + \cdots $$Step 2: Multiply the recurrence by $x^n$ and sum
The recurrence holds for $n \ge 2$. Multiply 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. $$Each sum is $F(x)$ with terms missing or shifted. Working them out:
- Left side: $\displaystyle\sum_{n \ge 2} F_n x^n = F(x) - F_0 - F_1 x = F(x) - x$.
- First right-side sum: shift index $m = n - 1$, so $\displaystyle\sum_{n \ge 2} F_{n-1} x^n = x \sum_{m \ge 1} F_m x^m = x(F(x) - F_0) = x F(x)$.
- Second right-side sum: shift $m = n - 2$, so $\displaystyle\sum_{n \ge 2} F_{n-2} x^n = x^2 \sum_{m \ge 0} F_m x^m = x^2 F(x)$.
Assembled:
$$ F(x) - x \;=\; x F(x) + x^2 F(x). $$Step 3: Solve for $F(x)$
Move every $F(x)$ to the left:
$$ F(x) - x F(x) - x^2 F(x) \;=\; x $$ $$ F(x)\bigl(1 - x - x^2\bigr) \;=\; x $$ $$ \boxed{\;F(x) \;=\; \frac{x}{1 - x - x^2}\;} $$That is the ordinary generating function of the Fibonacci sequence. Pretty remarkable that an infinite sequence with no closed form (apparently) has a closed-form generating function.
Step 4: Partial-fraction decomposition
Factor the denominator. The roots of $1 - x - x^2 = 0$ are found via the quadratic formula on $x^2 + x - 1 = 0$ (after multiplying by $-1$):
$$ x \;=\; \frac{-1 \pm \sqrt{5}}{2}. $$Call them $x_+ = (-1 + \sqrt{5})/2 = 1/\varphi$ and $x_- = (-1 - \sqrt{5})/2 = 1/\psi$, where
$$ \varphi \;=\; \frac{1 + \sqrt{5}}{2} \quad\text{(the golden ratio)}, \qquad \psi \;=\; \frac{1 - \sqrt{5}}{2}. $$So $1 - x - x^2 = -(x - x_+)(x - x_-) = (1 - \varphi x)(1 - \psi x)$ — the second form is what we want because identity #4 ($1/(1 - ax) = \sum a^n x^n$) is keyed to the form $1 - (\text{root}) \cdot x$.
Now decompose:
$$ \frac{x}{(1 - \varphi x)(1 - \psi x)} \;=\; \frac{A}{1 - \varphi x} + \frac{B}{1 - \psi x}. $$Clearing denominators: $x = A(1 - \psi x) + B(1 - \varphi x)$. Match coefficients (constant: $A + B = 0$; coefficient of $x$: $-A\psi - B\varphi = 1$), or just plug in convenient values of $x$ — at $x = 1/\varphi$, the right side becomes $A(1 - \psi/\varphi)$, and the left side is $1/\varphi$. Solving gives
$$ A \;=\; \frac{1}{\sqrt{5}}, \qquad B \;=\; -\frac{1}{\sqrt{5}}. $$(The $\sqrt{5}$ appears because $\varphi - \psi = \sqrt{5}$.) So
$$ F(x) \;=\; \frac{1}{\sqrt{5}} \left( \frac{1}{1 - \varphi x} - \frac{1}{1 - \psi x} \right). $$Step 5: Extract $[x^n]$ using identity #4
Now apply $1/(1 - ax) = \sum a^n x^n$ term by term:
$$ F(x) \;=\; \frac{1}{\sqrt{5}} \sum_{n \ge 0} \varphi^n x^n \;-\; \frac{1}{\sqrt{5}} \sum_{n \ge 0} \psi^n x^n \;=\; \sum_{n \ge 0} \frac{\varphi^n - \psi^n}{\sqrt{5}} \, x^n. $$Reading off the coefficient gives Binet's formula:
$$ \boxed{\;F_n \;=\; \frac{\varphi^n - \psi^n}{\sqrt{5}} \;=\; \frac{1}{\sqrt{5}}\!\left(\!\left(\frac{1 + \sqrt{5}}{2}\right)^{\!n} - \left(\frac{1 - \sqrt{5}}{2}\right)^{\!n}\right)\!.\;} $$Sanity check at $n = 0, 1, 2, 5$: $F_0 = 0$, $F_1 = 1$, $F_2 = 1$, $F_5 = 5$. All correct — and we never had to guess the form of the solution, never had to verify it by induction. The algebra produced it.
The closed form $F_n = (\varphi^n - \psi^n)/\sqrt{5}$ had to look like a difference of $n$-th powers, because the generating function $F(x) = x/(1 - x - x^2)$ is a rational function whose denominator has two distinct roots. Every linear recurrence with constant coefficients has this structure: $a_n$ is a linear combination of $n$-th powers of the recurrence's characteristic roots. Generating functions explain why.
8. Exponential generating functions
So far every coin, ball, and Fibonacci number has been unlabeled: indistinguishable units. When the objects you are counting are labeled — students, colors, distinguishable positions — the ordinary generating function stops doing the right thing, and you switch to its labeled cousin.
For a sequence $a_0, a_1, a_2, \ldots$, the exponential generating function is
$$ A(x) \;=\; \sum_{n \ge 0} a_n \, \frac{x^n}{n!}. $$The $n!$ in the denominator absorbs the labels — the over-counting of arrangements that the OGF does not handle.
The key difference from the OGF is the convolution rule. If $C(x) = A(x) B(x)$ as EGFs, then
$$ c_n \;=\; \sum_{k=0}^{n} \binom{n}{k} a_k\, b_{n-k}. $$That extra $\binom{n}{k}$ counts the ways to split a labeled set of size $n$ into two labeled pieces of sizes $k$ and $n-k$ — exactly what you want for distinguishable objects.
Two examples to know:
- The EGF of the all-ones sequence is $\sum x^n/n! = e^x$. Where the OGF of $(1,1,\ldots)$ was $1/(1-x)$, the EGF is the exponential function — hence the name.
- The EGF of derangements $D_n$ (permutations with no fixed points) is $e^{-x}/(1-x)$, a small algebraic object that encodes a surprisingly rich sequence.
EGFs are the right tool for labeled structures: permutations with constraints, set partitions, graphs on labeled vertices, and most of the symbolic-method machinery of analytic combinatorics. They deserve a topic of their own — for now, remember the rule: unlabeled → OGF; labeled → EGF.
9. Common pitfalls
The recurrence $a_n = 2a_{n-1}$ does not pin down a sequence — you need $a_0$ as well. When you set up generating-function equations, the initial terms appear explicitly (as the "$F(x) - F_0 - F_1 x$" piece in the Fibonacci derivation). Skipping them gives the wrong $A(x)$.
For counting purposes a generating function is a formal object — you never need to ask whether the series converges. But the moment you want to plug in $x = 0.4$ to compute a probability, or extract asymptotics from a singularity, convergence matters. Keep the two modes separate in your head.
If $Q(x) = (1 - rx)^k$ with $k \ge 2$, partial fractions need terms $\frac{1}{(1 - rx)^j}$ for $j = 1, 2, \ldots, k$ — not just one $\frac{1}{1 - rx}$. The coefficient of $x^n$ in $1/(1 - rx)^k$ is $\binom{n + k - 1}{k - 1} r^n$ (identity #2 with $a$ folded in). Forgetting the higher-power terms gives the wrong coefficients.
OGF and EGF use the same notation but mean different things. Multiplying two OGFs treats objects as indistinguishable; multiplying two EGFs labels them. If you encode a labeled-object problem as an OGF, every formula you derive will be off by binomial coefficients. The cheap rule: if your sequence-of-interest is "number of ways to do X to a set of $n$ distinct things," reach for the EGF.
10. Worked examples
Example 1 · Solve $a_n = 3 a_{n-1}$ with $a_0 = 2$
Define $A(x) = \sum_{n \ge 0} a_n x^n$. Multiply the recurrence by $x^n$ and sum over $n \ge 1$:
$$ \sum_{n \ge 1} a_n x^n \;=\; 3 \sum_{n \ge 1} a_{n-1} x^n. $$The left side is $A(x) - a_0 = A(x) - 2$. The right side, after $m = n-1$, is $3x A(x)$. So
$$ A(x) - 2 = 3x A(x) \quad\Longrightarrow\quad A(x) = \frac{2}{1 - 3x}. $$By identity #4, $[x^n]\, A(x) = 2 \cdot 3^n$. So $a_n = 2 \cdot 3^n$ — which of course we could have guessed, but the method works the same whether the answer is guessable or not.
Example 2 · Coefficient of $x^{10}$ in $1/(1 - x)^4$
By identity #2 with $k = 4$:
$$ [x^{10}] \frac{1}{(1 - x)^4} \;=\; \binom{10 + 4 - 1}{4 - 1} \;=\; \binom{13}{3} \;=\; 286. $$This is the number of ways to distribute 10 identical balls into 4 distinguishable boxes — stars and bars, computed without drawing a single bar.
Example 3 · Number of ways to make 30¢ with pennies, nickels, dimes
$C(x) = \dfrac{1}{(1 - x)(1 - x^5)(1 - x^{10})}$. We want $[x^{30}]\, C(x)$.
Strategy: condition on the number of dimes $d \in \{0, 1, 2, 3\}$. For each, we need to make $30 - 10d$ cents using pennies and nickels, which is $\lfloor (30 - 10d)/5 \rfloor + 1$ ways (one for each choice of nickel count from $0$ to $\lfloor (30-10d)/5 \rfloor$).
- $d = 0$: 30¢ in p/n $\to 7$ ways (0–6 nickels)
- $d = 1$: 20¢ in p/n $\to 5$ ways
- $d = 2$: 10¢ in p/n $\to 3$ ways
- $d = 3$: 0¢ in p/n $\to 1$ way
Total: $7 + 5 + 3 + 1 = 16$ ways. Sanity check against the generating function by expanding $C(x)$ symbolically — the coefficient of $x^{30}$ is indeed 16.
Example 4 · Solve $a_n = 5 a_{n-1} - 6 a_{n-2}$ with $a_0 = 0$, $a_1 = 1$
Set $A(x) = \sum a_n x^n$. Multiplying the recurrence by $x^n$ and summing for $n \ge 2$:
$$ A(x) - a_0 - a_1 x \;=\; 5x\bigl(A(x) - a_0\bigr) - 6x^2 A(x). $$Substituting initial conditions: $A(x) - x = 5x A(x) - 6 x^2 A(x)$, so
$$ A(x)\bigl(1 - 5x + 6 x^2\bigr) = x \quad\Longrightarrow\quad A(x) = \frac{x}{1 - 5x + 6 x^2}. $$Factor: $1 - 5x + 6x^2 = (1 - 2x)(1 - 3x)$. Partial fractions:
$$ \frac{x}{(1 - 2x)(1 - 3x)} = \frac{-1}{1 - 2x} + \frac{1}{1 - 3x}. $$Apply identity #4 term by term:
$$ a_n = -2^n + 3^n = 3^n - 2^n. $$Check: $a_0 = 1 - 1 = 0$ ✓; $a_1 = 3 - 2 = 1$ ✓; $a_2 = 9 - 4 = 5 = 5(1) - 6(0)$ ✓.
Example 5 · Derive $\sum_{k=0}^{n} \binom{n}{k} = 2^n$ from generating functions
By the binomial theorem, $(1 + x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k$. Evaluate at $x = 1$:
$$ 2^n \;=\; (1 + 1)^n \;=\; \sum_{k=0}^{n} \binom{n}{k}. $$One of the cleanest examples of "treat $x$ as a real number when you want to extract a value." The generating function is a polynomial here, so there is no convergence question.