Contents / Combinatorics / Generating Functions

Chapter 3

Generating Functions

Formal power series as a bookkeeping device for counting, and the recurrences they solve in closed form.

Introduction

Formal power series as a bookkeeping device for counting, and the recurrences they solve in closed form.

3.1Formal Power Series and Ordinary Generating Functions

Before any counting, we need the objects we will be computing with. The temptation is to think of $1 + x + x^{2} + \dots$ as a function of a real variable $x$ , defined where the series converges. That reading is available, and much later it becomes useful, but as a foundation it is a mistake: it makes every algebraic step conditional on an analytic question that has nothing to do with the combinatorics.

Definition 3.1 (Formal power series). Let $K$ be a field (for us almost always $Q$ , $R$ or $C$ ). A formal power series over $K$ is an infinite sequence

A = (a_{0}, a_{1}, a_{2}, \dots), a_{n} \in K,

written suggestively as $A (x) = \sum_{n \geq 0} a_{n} x^{n}$ . The set of all such series is written $K [[x]]$ . Two series are equal exactly when their coefficient sequences are equal, term by term. We write $[x^{n}] A (x) = a_{n}$ for the coefficient-extraction operator.

The symbol $x$ is a placeholder — a bookkeeping device that records which coefficient is which. Nothing is ever substituted into it, so nothing needs to converge. Addition and multiplication are defined directly on coefficients.

Definition 3.2 (The ring operations). For $A = \sum a_{n} x^{n}$ and $B = \sum b_{n} x^{n}$ in $K [[x]]$ ,

[x^{n}] (A + B) = a_{n} + b_{n}, [x^{n}] (A \cdot B) = k = 0 \sum n a_{k} b_{n - k} .

The second is the Cauchy product, or convolution, of the two coefficient sequences.

Observe that the product is well defined with no limiting process at all: the coefficient of $x^{n}$ is a finite sum of $n + 1$ terms. This is the whole reason formal power series work. Each coefficient of the answer is determined by finitely much of the input.

Theorem 3.3 ( $K [[x]]$ is a commutative ring). With the operations of the definition of the ring operations, $K [[x]]$ is a commutative ring with additive identity $0 = (0, 0, \dots)$ and multiplicative identity $1 = (1, 0, 0, \dots)$ . Moreover it is an integral domain: if $A \neq = 0$ and $B \neq = 0$ then $A B \neq = 0$ .

Proof. Commutativity and associativity of addition are inherited coefficientwise from $K$ . For the product, commutativity is the substitution $k \mapsto n - k$ in the convolution. For associativity, both $(A B) C$ and $A (BC)$ have

[x^{n}] = i + j + k = n \sum a_{i} b_{j} c_{k},

a finite sum over ordered triples, so they agree. Distributivity is likewise immediate coefficientwise.

For the integral-domain claim, let $i$ be least with $a_{i} \neq = 0$ and $j$ least with $b_{j} \neq = 0$ — these exist because $A$ and $B$ are non-zero. Then

[x^{i + j}] (A B) = k = 0 \sum i + j a_{k} b_{i + j - k} = a_{i} b_{j},

because every other term has either $k < i$ (so $a_{k} = 0$ ) or $k > i$ , forcing $i + j - k < j$ (so $b_{i + j - k} = 0$ ). Since $K$ is a field and $a_{i}, b_{j} \neq = 0$ , we get $a_{i} b_{j} \neq = 0$ , so $A B \neq = 0$ .∎

The index $i$ appearing in that proof is worth a name.

Definition 3.4 (Order and valuation). The order $ord (A)$ of a non-zero $A \in K [[x]]$ is the least $n$ with $a_{n} \neq = 0$ ; we set $ord (0) = \infty$ . The proof above shows $ord (A B) = ord (A) + ord (B)$ .

Remark (Why convergence is not the point). The series $\sum_{n \geq 0} n! x^{n}$ converges for no real $x$ except $0$ . As a formal power series it is a perfectly ordinary element of $Q [[x]]$ : it is the sequence $(1, 1, 2, 6, 24, \dots)$ , it can be added to and multiplied by anything, and it has a multiplicative inverse (the Units Theorem). Its coefficients answer a genuine counting question — how many permutations of an $n$ -element set there are — and no analytic statement about it is needed to do that counting. Insisting on convergence would discard a legitimate and useful object for a reason external to the problem.

Conversely, when a generating function does converge near $0$ , that is a bonus: it opens the door to estimating $a_{n}$ by studying the singularities of the analytic function. That subject — singularity analysis, the analytic combinatorics of Flajolet and Sedgewick — is beyond this chapter, and we will flag the one or two places where we lean on it.

Division needs an argument, and the argument is the reason the geometric series identity is true rather than merely suggestive.

Theorem 3.5 (Units of $K [[x]]$ ). A formal power series $A \in K [[x]]$ has a multiplicative inverse in $K [[x]]$ if and only if $a_{0} \neq = 0$ . The inverse is unique.

Proof. ( $\Rightarrow$ ) If $A B = 1$ then comparing constant terms gives $a_{0} b_{0} = 1$ , so $a_{0} \neq = 0$ .

( $\Leftarrow$ ) Suppose $a_{0} \neq = 0$ . We must produce $b_{0}, b_{1}, b_{2}, \dots$ with $\sum_{k = 0}^{n} a_{k} b_{n - k} = [n = 0]$ . For $n = 0$ this forces $b_{0} = a_{0}^{- 1}$ , which exists because $K$ is a field. For $n \geq 1$ the condition reads

a_{0} b_{n} + k = 1 \sum n a_{k} b_{n - k} = 0, that is b_{n} = - \frac{1}{a _{0}} k = 1 \sum n a_{k} b_{n - k} .

The right-hand side involves only $b_{0}, \dots, b_{n - 1}$ , so this recursion determines $b_{n}$ uniquely from the previously determined coefficients. By induction every $b_{n}$ exists and is unique, and the resulting $B$ satisfies $A B = 1$ .∎

Corollary 3.6 (The geometric series). In $K [[x]]$ ,

\frac{1}{1 - x} = n \geq 0 \sum x^{n}, and more generally \frac{1}{1 - c x} = n \geq 0 \sum c^{n} x^{n}

for any $c \in K$ .

Proof. By the Units Theorem the series $1 - c x$ has a unique inverse, so it suffices to check that $\sum_{n \geq 0} c^{n} x^{n}$ works. Its product with $1 - c x$ has

[x^{n}] = c^{n} - c \cdot c^{n - 1} = 0 (n \geq 1), [x^{0}] = 1,

so the product is $1$ . Uniqueness of inverses finishes it.∎

Intuition. The verification above is the entire content of "the geometric series". We are not summing infinitely many numbers; we are exhibiting the sequence $(1, 1, 1, \dots)$ as the unique sequence whose convolution with $(1, - c, 0, 0, \dots)$ is $(1, 0, 0, \dots)$ . Every coefficient check is a one-line finite cancellation. That is why the identity holds "for all $x$ ", including $x = 2$ , where the numerical series diverges wildly: there is no $x$ .

Pitfall (Do not evaluate a formal series at a number). Writing $\frac{1}{1 - 2} = 1 + 2 + 4 + 8 + \dots = - 1$ is not a clever formal-series fact; it is a category error. A formal power series is an element of $K [[x]]$ , not a function. The one substitution that is always legitimate is $x = 0$ , which reads off the constant term. Substituting another series is legitimate under a condition given in the Composition Theorem below.

With the ring in place we can finally say what a generating function is.

Definition 3.7 (Ordinary generating function). The ordinary generating function (OGF) of a sequence $a_{0}, a_{1}, a_{2}, \dots$ is the formal power series

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

If $C$ is a set of combinatorial objects equipped with a size function $∣ \cdot ∣ : C \to Z_{\geq 0}$ taking each value finitely often, the OGF of the class $C$ is

C (x) = c \in C \sum x^{∣ c ∣} = n \geq 0 \sum c_{n} x^{n}, c_{n} = # {c \in C : ∣ c ∣ = n} .

The second formulation — sum $x^{∣ c ∣}$ over the objects themselves — is the one to keep in mind, because it makes the product rule obvious later. The exponent marks the parameter being counted, and the coefficient of $x^{n}$ is the answer to the counting question at size $n$ .

Intuition. Think of $A (x)$ as a filing cabinet with one drawer per size. Drawer $n$ contains the number $a_{n}$ , and the symbol $x^{n}$ is the label on the drawer. Algebra on generating functions is a way of manipulating the whole cabinet at once: multiplying two cabinets combines their contents in every way whose sizes add up, which is exactly the "choose one of these and one of those" step that counting arguments are made of.

Example 3.8 (The OGF of a finite class). Find the generating function that counts the subsets of an $n$ -element set by their size.

Solution. Let $C$ be the class of subsets $S \subseteq {1, \dots, n}$ with $∣ S ∣$ its cardinality. Then

C (x) = S \sum x^{∣ S ∣} = k = 0 \sum n (k n) x^{k} = (1 + x)^{n},

the last step being the binomial theorem. Read backwards this is a proof of the binomial theorem by generating functions: a subset is built by deciding, independently for each of the $n$ elements, to exclude it (contributing $x^{0} = 1$ ) or include it (contributing $x^{1}$ ), so the class is a product of $n$ two-element classes each with generating function $1 + x$ .

The generating function here is a polynomial — a formal power series that happens to have finitely many non-zero coefficients. Polynomials are exactly the elements of $K [[x]]$ of that shape, and nothing about the theory changes.□

Two more pieces of infrastructure are needed before the dictionary of operations: infinite sums and substitution. Both are legitimate in $K [[x]]$ under a finiteness condition.

Definition 3.9 (Summable family). A family $(A^{(i)})_{i \in I}$ of formal power series is summable if for every $n$ only finitely many $i \in I$ have $[x^{n}] A^{(i)} \neq = 0$ . Its sum is then defined coefficientwise:

[x^{n}] i \in I \sum A^{(i)} = i \in I \sum [x^{n}] A^{(i)},

a finite sum for each $n$ .

Theorem 3.10 (Composition of formal power series). Let $A = \sum_{k \geq 0} a_{k} x^{k}$ and let $B \in K [[x]]$ with $b_{0} = 0$ . Then the family $(a_{k} B^{k})_{k \geq 0}$ is summable, so

A (B (x)) := k \geq 0 \sum a_{k} B (x)^{k}

is a well-defined element of $K [[x]]$ . If $b_{0} \neq = 0$ and infinitely many $a_{k}$ are non-zero, the family is in general not summable and the composition is undefined.

Proof. Since $b_{0} = 0$ we have $ord (B) \geq 1$ , hence $ord (B^{k}) \geq k$ by the order of a product. So for fixed $n$ , every term with $k > n$ contributes $0$ to $[x^{n}]$ , leaving at most $n + 1$ contributing terms: the family is summable.

For the failure case, take $B = 1$ (so $b_{0} = 1$ ) and $A = \sum_{k} x^{k}$ . Then $a_{k} B^{k} = 1$ for every $k$ , and every one of them contributes to $[x^{0}]$ ; the constant term would be an infinite sum of $1$ 's, which is not an element of $K$ .∎

This is the precise reason for a condition that will recur constantly: constructions like $\frac{1}{1 - A ( x )}$ require $a_{0} = 0$ . It is not a convergence scruple imported from analysis; it is the difference between a defined and an undefined expression in $K [[x]]$ .

Example 3.11 (A first counting problem). In how many ways can $n$ cents be paid using only 1-cent coins? Write the OGF and identify it in closed form.

Solution. For each $n \geq 0$ there is exactly one such payment (use $n$ pennies), so $a_{n} = 1$ for all $n$ and

A (x) = n \geq 0 \sum x^{n} = \frac{1}{1 - x}

by the geometric series identity. Equivalently, and more usefully for what follows: the class of payments is the class of finite multisets of pennies, one object of each size, and $\sum_{c} x^{∣ c ∣} = \sum_{n \geq 0} x^{n}$ .

The closed form is not an answer in itself — the answer was $1$ and we knew it. Its value is that $\frac{1}{1 - x}$ is a factor we can multiply by other factors, which is what makes the two-coin and ten-coin versions of the question tractable.□

Exercises for §3.1 →

3.2The Algebra of Generating Functions

Everything in this chapter rests on a dictionary: a table translating operations on sequences into operations on their generating functions, and combinatorial constructions into algebra. This section states the dictionary and proves it.

Theorem 3.12 (Dictionary of coefficient operations). Let $A (x) = \sum_{n \geq 0} a_{n} x^{n}$ and $B (x) = \sum_{n \geq 0} b_{n} x^{n}$ and let $c \in K$ , $m \in Z_{\geq 0}$ . Then:

Linear combination. $α A (x) + βB (x)$ is the OGF of $(α a_{n} + β b_{n})$ .
Product. $A (x) B (x)$ is the OGF of the convolution $(\sum_{k = 0}^{n} a_{k} b_{n - k})_{n \geq 0}$ .
Right shift. $x^{m} A (x)$ is the OGF of the sequence that is $0$ for $n < m$ and $a_{n - m}$ for $n \geq m$ .
Left shift. $\frac{A ( x ) - a _{0} - a _{1} x - \dots - a _{m - 1} x ^{m - 1}}{x ^{m}}$ is the OGF of $(a_{n + m})_{n \geq 0}$ .
Rescaling. $A (c x)$ is the OGF of $(c^{n} a_{n})$ , and $A (x^{m})$ is the OGF of the sequence with $a_{k}$ in position $mk$ and $0$ elsewhere.
Multiplication by $n$ . $x A^{'} (x)$ is the OGF of $(n a_{n})$ , where $A^{'} (x) := \sum_{n \geq 1} n a_{n} x^{n - 1}$ is the formal derivative.
Partial sums. $\frac{A ( x )}{1 - x}$ is the OGF of $(\sum_{k = 0}^{n} a_{k})_{n \geq 0}$ .

Proof. (1) and (2) are the definition of the ring operations restated. (3) is immediate: $x^{m} \sum a_{n} x^{n} = \sum a_{n} x^{n + m}$ , and reindexing $n^{'} = n + m$ gives coefficient $a_{n^{'} - m}$ in position $n^{'}$ .

(4) The numerator has order at least $m$ , so it equals $\sum_{n \geq m} a_{n} x^{n}$ ; dividing by $x^{m}$ — which is exact, no inverse required — gives $\sum_{n \geq m} a_{n} x^{n - m} = \sum_{k \geq 0} a_{k + m} x^{k}$ .

(5) $A (c x) = \sum a_{n} c^{n} x^{n}$ by the Composition Theorem applied to $B = c x$ , which has $b_{0} = 0$ ; similarly for $x^{m}$ .

(6) $x A^{'} (x) = x \sum_{n \geq 1} n a_{n} x^{n - 1} = \sum_{n \geq 1} n a_{n} x^{n}$ , and the missing $n = 0$ term is $0 \cdot a_{0} = 0$ .

(7) By (2), $[x^{n}] \frac{A ( x )}{1 - x} = \sum_{k = 0}^{n} a_{k} \cdot 1 = \sum_{k = 0}^{n} a_{k}$ , using the geometric series identity to write $\frac{1}{1 - x} = \sum x^{n}$ .∎

Notation (The formal derivative). $A^{'} (x) = \sum_{n \geq 1} n a_{n} x^{n - 1}$ is defined by that formula, not by a limit. It satisfies the usual rules — $(A B)^{'} = A^{'} B + A B^{'}$ and $(A (B))^{'} = A^{'} (B) \cdot B^{'}$ when the composition is defined — each provable by comparing coefficients, and we use them freely. In characteristic $0$ , $A^{'} = 0$ if and only if $A$ is a constant.

The product rule deserves its own statement, because it is the rule that turns combinatorics into algebra.

Theorem 3.13 (Product rule for combinatorial classes). Let $A$ and $B$ be classes with OGFs $A (x)$ and $B (x)$ , and let $C = A \times B$ be the class of ordered pairs $(a, b)$ with size $∣ (a, b) ∣ = ∣ a ∣ + ∣ b ∣$ . Then

C (x) = A (x) B (x) .

Consequently, if a class $C$ admits an unambiguous decomposition — a bijection between its objects and pairs from $A \times B$ that adds sizes — then $C (x) = A (x) B (x)$ .

Proof. Using the object-sum form of the definition of an OGF,

A (x) B (x) = (a \in A \sum x^{∣ a ∣}) (b \in B \sum x^{∣ b ∣}) = (a, b) \in A \times B \sum x^{∣ a ∣ + ∣ b ∣} = c \in C \sum x^{∣ c ∣},

where the middle equality is legitimate because for each $n$ only finitely many pairs have $∣ a ∣ + ∣ b ∣ = n$ (each class has finitely many objects of each size, and there are finitely many splits $n = i + j$ ). Comparing coefficients of $x^{n}$ gives precisely $c_{n} = \sum_{k} a_{k} b_{n - k}$ .∎

Intuition. The convolution $\sum_{k} a_{k} b_{n - k}$ is the sentence "to build an object of size $n$ , choose how much of the size goes to the first component — say $k$ — then choose one of the $a_{k}$ first components and, independently, one of the $b_{n - k}$ second components; sum over $k$ because the choices of $k$ are disjoint." Multiplication of series is the mechanised version of that sentence. Every time you would have written a case analysis with a sum over a split point, you can instead write a product.

The word "unambiguous" is load-bearing. Each object of $C$ must arise from exactly one pair. If some object can be split in two different ways, the product over-counts.

Theorem 3.14 (Sequence construction). Let $A$ be a class with $a_{0} = 0$ (no objects of size $0$ ) and OGF $A (x)$ . Let $SEQ (A)$ be the class of finite sequences $(α_{1}, \dots, α_{k})$ , $k \geq 0$ , of objects from $A$ , with size the sum of the component sizes. Then

OGF of SEQ (A) = k \geq 0 \sum A (x)^{k} = \frac{1}{1 - A ( x )} .

Proof. Sequences of length exactly $k$ form the class $A^{k}$ , whose OGF is $A (x)^{k}$ by $k - 1$ applications of the Product Rule. The classes of different lengths are disjoint, and since $a_{0} = 0$ we have $ord (A^{k}) \geq k$ , so the family $(A^{k})_{k \geq 0}$ is summable (summability) and the class union has OGF $\sum_{k \geq 0} A (x)^{k}$ .

It remains to see that this sum is the inverse of $1 - A (x)$ . Write $S = \sum_{k \geq 0} A^{k}$ . Then

(1 - A) S = k \geq 0 \sum A^{k} - k \geq 0 \sum A^{k + 1} = A^{0} = 1,

where the rearrangement is valid coefficientwise because each coefficient involves only finitely many terms. Since $1 - A$ has constant term $1 \neq = 0$ it is a unit (the Units Theorem) with unique inverse, so $S = \frac{1}{1 - A}$ .∎

Pitfall (The $a_{0} = 0$ condition is not optional). If $A$ contained an object of size $0$ , a "sequence" could contain arbitrarily many copies of it without growing, so there would be infinitely many sequences of size $0$ and no generating function at all — the class is not admissible. On the algebraic side the family $(A^{k})$ fails to be summable and $\sum_{k} A^{k}$ is undefined, exactly as in the Composition Theorem. The symptom is an infinite constant term; the cause is a combinatorial construction that produces infinitely many objects of one size.

For coefficient extraction, one identity does most of the work. It is the binomial theorem, generalised so that the exponent need not be a non-negative integer.

Definition 3.15 (Generalised binomial coefficient). For $α \in K$ (or $α \in C$ ) and $n \in Z_{\geq 0}$ ,

(n α) = \frac{α ( α - 1 ) \dots ( α - n + 1 )}{n !},

with $(0 α) = 1$ . When $α$ is a non-negative integer this is the usual binomial coefficient and vanishes for $n > α$ ; otherwise it is non-zero for every $n$ .

Definition 3.16 (The series $(1 + x)^{α}$ ). For $α \in K$ we define

(1 + x)^{α} := n \geq 0 \sum (n α) x^{n} \in K [[x]] .

That is a definition, so nothing is yet proved; what has to be proved is that the notation is honest — that this series behaves like a power.

Theorem 3.17 (Generalised binomial theorem). For all $α, β \in K$ (char $K = 0$ ):

(1 + x)^{α} (1 + x)^{β} = (1 + x)^{α + β}, (1 + x)^{0} = 1, (1 + x)^{1} = 1 + x,

and $\frac{d}{d x} (1 + x)^{α} = α (1 + x)^{α - 1}$ . In particular $(1 + x)^{- 1}$ is the inverse of $1 + x$ , and for $m$ a positive integer the definition of $(1 + x)^{α}$ agrees with the ordinary $m$ -fold product.

Proof. The product identity is equivalent, on comparing coefficients of $x^{n}$ , to the Vandermonde convolution

k = 0 \sum n (k α) (n - k β) = (n α + β) .

Both sides are polynomials in $α$ and $β$ of degree at most $n$ in each. For non-negative integers $α, β$ the identity is the standard combinatorial Vandermonde identity: choosing $n$ elements from a set of $α + β$ elements split into blocks of sizes $α$ and $β$ amounts to choosing $k$ from the first and $n - k$ from the second. A polynomial in two variables that vanishes at all pairs of non-negative integers is identically zero (fix $β$ integral and note a one-variable polynomial with infinitely many roots is zero; then repeat in $β$ ). Hence the identity holds for all $α, β \in K$ .

The cases $α = 0, 1$ are immediate from the definition of $(n α)$ . The derivative claim follows from $n (n α) = α (n - 1 α - 1)$ , which is a direct computation from the definition. Finally, $(1 + x)^{m}$ for a positive integer $m$ is a product of $m$ copies of $(1 + x)^{1} = 1 + x$ by the first identity and induction.∎

Corollary 3.18 (Negative exponents). For an integer $k \geq 1$ ,

\frac{1}{( 1 - x ) ^{k}} = n \geq 0 \sum (k - 1 n + k - 1) x^{n} = n \geq 0 \sum (n n + k - 1) x^{n} .

Proof. By the Generalised Binomial Theorem, $(1 + y)^{- k} = \sum_{n} (n - k) y^{n}$ is the inverse of $(1 + y)^{k}$ . Substituting $y = - x$ (valid by the Composition Theorem) gives $\frac{1}{( 1 - x ) ^{k}} = \sum_{n} (n - k) (- 1)^{n} x^{n}$ . Now compute

(n - k) (- 1)^{n} = (- 1)^{n} \frac{( - k ) ( - k - 1 ) \dots ( - k - n + 1 )}{n !} = \frac{k ( k + 1 ) \dots ( k + n - 1 )}{n !} = (n n + k - 1),

since the $n$ factors each contribute one sign. The two binomial forms agree by symmetry.∎

Intuition. the negative-exponent corollary has a purely combinatorial reading, and it is worth seeing both. $\frac{1}{( 1 - x ) ^{k}}$ is the product of $k$ copies of $\frac{1}{1 - x}$ , so by the Product Rule its $n$ -th coefficient counts the ways to write $n = n_{1} + \dots + n_{k}$ with each $n_{i} \geq 0$ — the number of ways to distribute $n$ identical balls into $k$ labelled boxes. Stars and bars says that number is $(k - 1 n + k - 1)$ . So the algebra and the combinatorics prove the same identity from opposite ends.

Example 3.19 (Two unlimited supplies). An unlimited supply of identical apples and an unlimited supply of identical oranges are available. In how many ways can one hold a total of $n$ fruit?

Solution. Holdings of apples form a class with one object of each size, OGF $\frac{1}{1 - x}$ ; likewise for oranges. A holding is an ordered pair (apple part, orange part) with sizes adding, so by the Product Rule the OGF is

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

By the negative-exponent corollary with $k = 2$ , the coefficient of $x^{n}$ is $(1 n + 1) = n + 1$ .

Check directly: choose $k \in {0, 1, \dots, n}$ apples and take the remaining $n - k$ as oranges — $n + 1$ choices, as computed.□

Example 3.20 (Coefficients of a rational function). Find $[x^{n}] \frac{1 + x}{( 1 - x ) ^{3}}$ .

Solution. Split the numerator and use linearity together with the right-shift rule (the Dictionary of Coefficient Operations, parts 1 and 3):

[x^{n}] \frac{1 + x}{( 1 - x ) ^{3}} = [x^{n}] \frac{1}{( 1 - x ) ^{3}} + [x^{n - 1}] \frac{1}{( 1 - x ) ^{3}} .

By the negative-exponent corollary with $k = 3$ these are $(2 n + 2)$ and $(2 n + 1)$ , so

[x^{n}] \frac{1 + x}{( 1 - x ) ^{3}} = \frac{( n + 2 ) ( n + 1 )}{2} + \frac{( n + 1 ) n}{2} = (n + 1)^{2} .

For $n = 0, 1, 2$ this predicts $1, 4, 9$ ; expanding $\frac{1}{( 1 - x ) ^{3}} = 1 + 3 x + 6 x^{2} + \dots$ and multiplying by $1 + x$ gives $1 + 4 x + 9 x^{2} + \dots$ , as claimed. (The answer is the sum of the first $n + 1$ odd numbers — a pleasant check, since $\frac{1 + x}{( 1 - x ) ^{3}} = \frac{1}{1 - x} \cdot \frac{1 + x}{( 1 - x ) ^{2}}$ and $\frac{1 + x}{( 1 - x ) ^{2}}$ is the OGF of the odd numbers.)□

Exercises for §3.2 →

3.3Solving Counting Problems with Generating Functions

We now put the dictionary to work. The pattern is always the same: describe the objects by an unambiguous construction, translate the construction into an equation between generating functions, and then extract coefficients by whatever algebraic means are available.

Method 3.21 (The generating-function method).

Specify. Describe the class by a decomposition built out of disjoint unions, products and sequences, in a way that produces each object exactly once.
Translate. Apply Theorems the Product Rule and the Sequence Construction theorem to get a formula or an equation for the OGF.
Solve. If the translation gave an equation (rather than a formula), solve it algebraically for the unknown series.
Extract. Recover $[x^{n}]$ by partial fractions, the generalised binomial theorem, or a convolution.
Check. Expand the first few coefficients by hand and compare against a direct count.

Example 3.22 (Compositions of an integer). A composition of $n$ is an ordered tuple of positive integers summing to $n$ ; for instance $3 = 3 = 2 + 1 = 1 + 2 = 1 + 1 + 1$ gives four compositions. Find the number of compositions of $n$ .

Solution. Specify. A composition is a sequence of parts, each part a positive integer. The class of parts has exactly one object of each size $k \geq 1$ , so its OGF is $P (x) = \sum_{k \geq 1} x^{k} = \frac{x}{1 - x}$ , with $p_{0} = 0$ as required.

Translate. By the Sequence Construction theorem,

C (x) = \frac{1}{1 - \frac{x}{1 - x}} = \frac{1 - x}{1 - 2 x} .

Extract. Write $\frac{1 - x}{1 - 2 x} = \frac{1}{1 - 2 x} - \frac{x}{1 - 2 x}$ . By the geometric series identity and the shift rule, the coefficient of $x^{n}$ is $2^{n} - 2^{n - 1} = 2^{n - 1}$ for $n \geq 1$ , and $c_{0} = 1$ .

Check. $c_{3} = 2^{2} = 4$ , matching the four compositions listed. The answer also has a one-line bijective proof (insert or omit a divider in each of the $n - 1$ gaps between $n$ units), which is a reminder that generating functions are one tool among several — but the method above needed no cleverness at all.□

Example 3.23 (Compositions with restricted parts). How many compositions of $n$ use only parts equal to $1$ or $2$ ?

Solution. The part class is now ${1, 2}$ with OGF $x + x^{2}$ , so the composition class has OGF

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

Its coefficients satisfy $c_{n} = c_{n - 1} + c_{n - 2}$ — we prove this properly in the Rationality Theorem — with $c_{0} = c_{1} = 1$ : the Fibonacci numbers. So the number of such compositions of $n$ is $F_{n + 1}$ in the indexing $F_{0} = 0, F_{1} = 1$ .

For $n = 4$ : $1 + 1 + 1 + 1$ , $1 + 1 + 2$ , $1 + 2 + 1$ , $2 + 1 + 1$ , $2 + 2$ , which is $5 = c_{4}$ .□

Example 3.24 (Making change). In how many ways can $n$ cents be paid using pennies, nickels and dimes ( $1$ , $5$ and $10$ cents), the coins of each denomination being identical? Evaluate at $n = 20$ .

Solution. Specify. A payment is determined by the number of pennies, the number of nickels and the number of dimes — an ordered triple of independent choices whose values add to $n$ . The class of penny-piles has one object of each size $0, 1, 2, \dots$ , OGF $\frac{1}{1 - x}$ ; nickel-piles have one object of each size $0, 5, 10, \dots$ , OGF $\frac{1}{1 - x ^{5}}$ ; dime-piles, $\frac{1}{1 - x ^{10}}$ .

Translate.

D (x) = \frac{1}{( 1 - x ) ( 1 - x ^{5} ) ( 1 - x ^{10} )} .

Extract. Rather than partial-fraction a degree- $16$ denominator, note that the pennies simply absorb whatever the other coins leave, so the count is the number of pairs (nickels, dimes) with total at most $n$ . For $n = 20$ : with $0$ dimes we may use $0, \dots, 4$ nickels ( $5$ ways); with $1$ dime, $0, \dots, 2$ nickels ( $3$ ways); with $2$ dimes, $0$ nickels ( $1$ way). Total $9$ .

Check. The same reasoning at $n = 10$ gives $3 + 1 = 4$ payments: ten pennies, one nickel and five pennies, two nickels, one dime. Correct.□

Remark (The generating function as a data structure). The last example makes a point about what a generating function is for. It gave us no slick closed form — denumerants genuinely do not have one for general denominations — but it gave us an object we can compute with mechanically: multiply the three series out to order $n$ and read off the coefficient, an $O (n)$ operation per factor. When a problem has no closed form, "the coefficient of $x^{n}$ in this explicit rational function" is still a complete and usable answer, and it is the form in which computer algebra systems prefer to receive it.

Partitions are the classical proving ground, and Euler's product is the classical result.

Definition 3.25 (Integer partition). A partition of $n$ is a multiset of positive integers summing to $n$ ; equivalently a weakly decreasing tuple $λ_{1} \geq λ_{2} \geq \dots \geq λ_{r} > 0$ with $\sum λ_{i} = n$ . The number of partitions of $n$ is $p (n)$ , with $p (0) = 1$ (the empty partition).

Order does not matter for a partition, which is exactly what distinguishes it from a composition — and it is why the sequence construction is the wrong tool and a product over part sizes is the right one.

Theorem 3.26 (Euler's product formula). As formal power series,

n \geq 0 \sum p (n) x^{n} = k \geq 1 \prod \frac{1}{1 - x ^{k}} .

Proof. First, the infinite product is meaningful in $K [[x]]$ : the partial products $P_{m} (x) = \prod_{k = 1}^{m} \frac{1}{1 - x ^{k}}$ satisfy $P_{m + 1} - P_{m} = P_{m} (\frac{1}{1 - x ^{m + 1}} - 1)$ , and $\frac{1}{1 - x ^{m + 1}} - 1 = \frac{x ^{m + 1}}{1 - x ^{m + 1}}$ has order $m + 1$ . So the coefficient of $x^{n}$ in $P_{m}$ is the same for all $m \geq n$ , and we define $[x^{n}] \prod_{k \geq 1} \frac{1}{1 - x ^{k}}$ to be that stable value.

Now fix $m \geq n$ and expand the finite product. By the geometric series identity applied with $x^{k}$ in place of $x$ ,

P_{m} (x) = k = 1 \prod m (m_{k} \geq 0 \sum x^{k m_{k}}) = (m_{1}, \dots, m_{m}) \sum x^{1 m_{1} + 2 m_{2} + \dots + m m_{m}},

the sum over all tuples of non-negative integers; the regrouping is the Product Rule applied $m - 1$ times. A tuple $(m_{1}, \dots, m_{m})$ contributing to $x^{n}$ is exactly a choice of how many parts of each size $1, \dots, m$ to use, with the sizes totalling $n$ — that is, exactly a partition of $n$ into parts of size at most $m$ . Since $m \geq n$ , no partition of $n$ has a part larger than $m$ , so these are all the partitions of $n$ . Hence $[x^{n}] P_{m} = p (n)$ , and the stable value is $p (n)$ .∎

Intuition. Each factor $\frac{1}{1 - x ^{k}}$ is a little machine that decides, independently of the others, how many parts of size $k$ the partition will have: choosing the term $x^{k m_{k}}$ means "use $m_{k}$ parts of size $k$ ". Multiplying the machines forces their contributions to add to $n$ . Compare the factor $(1 + x^{k})$ , which offers only "use a part of size $k$ or do not" — that one counts partitions into distinct parts.

Theorem 3.27 (Euler: distinct parts and odd parts). For every $n$ , the number of partitions of $n$ into pairwise distinct parts equals the number of partitions of $n$ into odd parts.

Proof. By the reasoning of Euler's Product Formula, partitions into distinct parts have OGF $\prod_{k \geq 1} (1 + x^{k})$ — each part size is used at most once — and partitions into odd parts have OGF $\prod_{j \geq 0} \frac{1}{1 - x ^{2 j + 1}}$ . It suffices to show the two products are equal.

Use $1 + x^{k} = \frac{1 - x ^{2 k}}{1 - x ^{k}}$ , valid in $K [[x]]$ since $1 - x^{k}$ is a unit. Then, taking the product over $k = 1, \dots, m$ ,

k = 1 \prod m (1 + x^{k}) = \frac{\prod _{k = 1}^{m} ( 1 - x ^{2 k} )}{\prod _{k = 1}^{m} ( 1 - x ^{k} )} .

In the denominator split the factors into even $k = 2 j$ and odd $k$ . The even ones, $\prod_{j \leq m /2} (1 - x^{2 j})$ , cancel against the matching factors of the numerator, leaving

k = 1 \prod m (1 + x^{k}) = \frac{\prod _{m /2 < j \leq m} ( 1 - x ^{2 j} )}{\prod _{k \leq m, k odd} ( 1 - x ^{k} )} .

Every remaining numerator factor has the form $1 - x^{2 j}$ with $2 j > m$ , so it differs from $1$ only in degrees exceeding $m$ . Comparing coefficients of $x^{n}$ for any fixed $n$ and taking $m \geq n$ , those factors are invisible, and we get

[x^{n}] k \geq 1 \prod (1 + x^{k}) = [x^{n}] k odd \prod \frac{1}{1 - x ^{k}}

for every $n$ , which is the claim.∎

Example 3.28 (Computing $p (n)$ for small $n$ ). Compute $p (6)$ from Euler's product.

Solution. We only need parts of size at most $6$ , so work modulo $x^{7}$ and multiply in the factors one at a time. Write $P_{k}$ for the product of the first $k$ factors.

P_{1} = \frac{1}{1 - x} \equiv 1 + x + x^{2} + x^{3} + x^{4} + x^{5} + x^{6}

Multiplying by $\frac{1}{1 - x ^{2}}$ means "add to each coefficient the coefficient two places earlier", so $P_{2} \equiv 1 + x + 2 x^{2} + 2 x^{3} + 3 x^{4} + 3 x^{5} + 4 x^{6}$ .

Similarly, multiplying by $\frac{1}{1 - x ^{3}}$ adds the coefficient three places earlier: $P_{3} \equiv 1 + x + 2 x^{2} + 3 x^{3} + 4 x^{4} + 5 x^{5} + 7 x^{6}$ .

By $\frac{1}{1 - x ^{4}}$ : $P_{4} \equiv 1 + x + 2 x^{2} + 3 x^{3} + 5 x^{4} + 6 x^{5} + 9 x^{6}$ . By $\frac{1}{1 - x ^{5}}$ : $P_{5} \equiv 1 + x + 2 x^{2} + 3 x^{3} + 5 x^{4} + 7 x^{5} + 10 x^{6}$ . By $\frac{1}{1 - x ^{6}}$ : $P_{6} \equiv 1 + x + 2 x^{2} + 3 x^{3} + 5 x^{4} + 7 x^{5} + 11 x^{6}$ .

So $p (6) = 11$ . Listing them confirms it: $6$ ; $5 + 1$ ; $4 + 2$ ; $4 + 1 + 1$ ; $3 + 3$ ; $3 + 2 + 1$ ; $3 + 1 + 1 + 1$ ; $2 + 2 + 2$ ; $2 + 2 + 1 + 1$ ; $2 + 1 + 1 + 1 + 1$ ; $1^{6}$ .

Note the "multiply by $\frac{1}{1 - x ^{k}}$ " step is just the partial-sum rule of the Dictionary of Coefficient Operations(7) with $x^{k}$ in place of $x$ , which is why it is an in-place update and not a full convolution. That observation is the standard $O (n^{3/2})$ algorithm for tabulating $p (n)$ .□

Proposition 3.29 (Parts of bounded size versus boundedly many parts). The number of partitions of $n$ into at most $m$ parts equals the number of partitions of $n$ into parts of size at most $m$ ; both have OGF $\prod_{k = 1}^{m} \frac{1}{1 - x ^{k}}$ .

Proof. Represent a partition $λ_{1} \geq \dots \geq λ_{r}$ by its Young diagram: row $i$ consists of $λ_{i}$ cells. Reflecting the diagram in its main diagonal — replacing rows by columns — produces the diagram of another partition $λ^{*}$ of the same $n$ , the conjugate, and conjugation is an involution, hence a bijection. The number of rows of $λ$ is the size of the first column, which is the largest part of $λ^{*}$ ; so $λ$ has at most $m$ parts if and only if $λ^{*}$ has all parts at most $m$ . The generating function for the second family is the argument of Euler's Product Formula truncated at $k = m$ .∎

Figure 3.30. Conjugation reflects a Young diagram in its main diagonal. The three rows of

λ

become the largest part of

λ^{*}

, so "at most

m

parts" and "every part at most

m

" are the same condition read twice.

Exercises for §3.3 →

3.4Exponential Generating Functions

Ordinary generating functions are the right bookkeeping for unlabelled objects — piles of identical coins, partitions, tilings — where the only thing an object contributes is its size. They are the wrong bookkeeping for objects built on a set of distinguishable atoms: people, numbered positions, vertices of a labelled graph. For those, the number of structures grows factorially, and a different weighting is needed.

Definition 3.31 (Labelled class). A labelled class $A$ assigns, to each finite set $U$ of labels, a finite set $A [U]$ of structures on $U$ , in such a way that relabelling along a bijection $U \to V$ carries $A [U]$ bijectively onto $A [V]$ . Consequently $# A [U]$ depends only on $∣ U ∣$ , and we write $a_{n} = # A [{1, \dots, n}]$ .

Permutations, set partitions, labelled graphs, functions from $[n]$ to $[n]$ , and rooted labelled trees are all labelled classes in this sense.

Definition 3.32 (Exponential generating function). The exponential generating function (EGF) of a sequence $(a_{n})$ — equivalently, of a labelled class — is

A (x) = n \geq 0 \sum \frac{a _{n}}{n !} x^{n} .

To recover the count, multiply back: $a_{n} = n! [x^{n}] A (x)$ .

Notation (Hats). Where both bookkeepings are in play we write $A (x)$ for an OGF and $A (x)$ for an EGF of the same sequence. Elsewhere in this chapter, and in most of the literature, the hat is dropped and the reader is expected to know from context which is meant; the two are different series, and confusing them is the classic error of the subject.

Why divide by $n!$ ? Because of what happens when labelled structures are combined. If we place an $A$ -structure on part of a label set and a $B$ -structure on the rest, we must first choose which labels go where, and that choice contributes a binomial coefficient. The $n!$ in the denominator is engineered to absorb it.

Definition 3.33 (Labelled product). For labelled classes $A, B$ , the labelled product $A ⋆ B$ has, on the label set $U$ , all triples $(S, α, β)$ where $S \subseteq U$ , $α \in A [S]$ and $β \in B [U ∖ S]$ . In words: split the labels into two blocks, put an $A$ -structure on one and a $B$ -structure on the other.

Theorem 3.34 (Product rule for EGFs). If $C = A ⋆ B$ then

C (x) = A (x) B (x), equivalently c_{n} = k = 0 \sum n (k n) a_{k} b_{n - k} .

The second form is the binomial convolution.

Proof. Counting $C [[n]]$ directly: choose the block $S$ of size $k$ in $(k n)$ ways, then an $A$ -structure on it in $a_{k}$ ways (a number depending only on $k$ , by the definition of a labelled class), then a $B$ -structure on the complementary $n - k$ labels in $b_{n - k}$ ways. Summing over $k$ gives $c_{n} = \sum_{k} (k n) a_{k} b_{n - k}$ , and the choices are distinct for distinct $(S, α, β)$ , so nothing is double counted.

Now translate. The coefficient of $x^{n}$ in $A B$ is, by the Cauchy product,

k = 0 \sum n \frac{a _{k}}{k !} \cdot \frac{b _{n - k}}{( n - k )!} = \frac{1}{n !} k = 0 \sum n \frac{n !}{k ! ( n - k )!} a_{k} b_{n - k} = \frac{1}{n !} k = 0 \sum n (k n) a_{k} b_{n - k} = \frac{c _{n}}{n !},

which is exactly $[x^{n}] C (x)$ .∎

Intuition. The $\frac{1}{n !}$ is a normalisation that makes the factorials cancel at exactly the right moment. Multiplying OGFs performs the plain convolution $\sum a_{k} b_{n - k}$ , which answers "split the size"; multiplying EGFs performs the binomial convolution $\sum (k n) a_{k} b_{n - k}$ , which answers "split the labels". Both are "do one thing and then another", but for labelled objects the splitting is a choice of subset, not merely a choice of number, and the binomial coefficient is the price of that choice.

Proposition 3.35 (Dictionary for EGFs). Let $A (x) = \sum_{n \geq 0} a_{n} \frac{x ^{n}}{n !}$ . Then:

$A^{'} (x)$ is the EGF of the shifted sequence $(a_{n + 1})_{n \geq 0}$ .
$x A (x)$ is the EGF of $(n a_{n - 1})_{n \geq 0}$ (with the $n = 0$ term $0$ ).
$\int_{0}^{x} A := \sum_{n \geq 0} a_{n} \frac{x ^{n + 1}}{( n + 1 )!}$ is the EGF of $(a_{n - 1})_{n \geq 1}$ , extended by $0$ at $n = 0$ .
$e^{x}$ is the EGF of the constant sequence $1, 1, 1, \dots$ , and $\frac{1}{1 - x}$ is the EGF of $n!$ .

Proof. (1) $A^{'} (x) = \sum_{n \geq 1} n a_{n} \frac{x ^{n - 1}}{n !} = \sum_{n \geq 1} a_{n} \frac{x ^{n - 1}}{( n - 1 )!} = \sum_{m \geq 0} a_{m + 1} \frac{x ^{m}}{m !}$ .

(2) $x \cdot a_{n - 1} \frac{x ^{n - 1}}{( n - 1 )!} = a_{n - 1} \frac{x ^{n}}{( n - 1 )!} = n a_{n - 1} \frac{x ^{n}}{n !}$ .

(3) is (1) read backwards. (4) $e^{x} := \sum_{n} \frac{x ^{n}}{n !}$ , so $n! [x^{n}] e^{x} = 1$ ; and $\frac{1}{1 - x} = \sum_{n} x^{n}$ , so $n! [x^{n}] \frac{1}{1 - x} = n!$ .∎

Remark ( $e^{x}$ as a formal object). We define $e^{x}$ , $ln \frac{1}{1 - x}$ , $sin x$ and so on by their coefficient sequences, exactly as with $(1 + x)^{α}$ . The identities we need — $e^{A + B} = e^{A} e^{B}$ for $A, B$ of positive order, $ln \frac{1}{1 - x}$ as the inverse function of $e^{x} - 1$ under composition, $\frac{d}{d x} e^{x} = e^{x}$ — are then formal identities, provable by coefficient comparison or by the formal chain rule. None of this appeals to analysis; we are working inside $Q [[x]]$ throughout.

Example 3.36 (Permutations). Find the EGF for the number of permutations (linear orderings) of an $n$ -element labelled set, and recover $a_{n}$ .

Solution. There are $a_{n} = n!$ orderings of $[n]$ . Hence

A (x) = n \geq 0 \sum \frac{n !}{n !} x^{n} = n \geq 0 \sum x^{n} = \frac{1}{1 - x} .

Recovering: $a_{n} = n! [x^{n}] \frac{1}{1 - x} = n! \cdot 1 = n!$ , as it should be.

Contrast the OGF of the same sequence, $\sum_{n} n! x^{n}$ , which has no closed form of any standard kind (its formal inverse is computable but unilluminating). This is the first evidence of the general principle: for labelled objects, the EGF is the series with the simple closed form.□

Example 3.37 (Words over an alphabet). Let $a_{n}$ be the number of ways to colour $n$ labelled objects with $r$ available colours. Find the EGF.

Solution. Colouring the objects means choosing, independently for each of the $n$ labels, one of $r$ colours: $a_{n} = r^{n}$ . So

A (x) = n \geq 0 \sum \frac{r ^{n} x ^{n}}{n !} = e^{r x} = (e^{x})^{r} .

The factorisation $(e^{x})^{r}$ is itself the statement being proved: a colouring is a labelled product of $r$ blocks (the colour classes), each of which is an arbitrary set of labels carrying no further structure, and "an arbitrary set of labels" has EGF $\sum_{n} \frac{x ^{n}}{n !} = e^{x}$ since there is exactly one such structure on each label set. The EGF product rule then multiplies the $r$ factors.□

Pitfall (The coefficient is not the count). $[x^{n}] A (x)$ is $\frac{a _{n}}{n !}$ , not $a_{n}$ . Forgetting the multiplier is the single most common slip with EGFs, and it is silent: $\frac{a _{n}}{n !}$ is usually a plausible-looking rational number. Whenever you finish an EGF computation, the last line should be "multiply by $n!$ ".

Exercises for §3.4 →

3.5Labelled Structures and the Exponential Formula

The payoff of the $\frac{1}{n !}$ normalisation is a dictionary of constructions as clean as the ordinary one, and one theorem — the exponential formula — that has no ordinary analogue of comparable simplicity.

Theorem 3.38 (Constructions on labelled classes). Let $A$ be a labelled class with $a_{0} = 0$ (no structure on the empty label set) and EGF $A (x)$ . Then:

Sequence. The class of sequences $(α_{1}, \dots, α_{k})$ , $k \geq 0$ , of $A$ -structures on the blocks of an ordered set partition of the labels has EGF $\frac{1}{1 - A ( x )}$ .
Set. The class whose structures are sets of $A$ -structures on the blocks of an (unordered) set partition of the labels has EGF $exp (A (x))$ .
Cycle. The class of cyclic arrangements of $A$ -structures has EGF $ln \frac{1}{1 - A ( x )}$ .

Proof. (1) Sequences of exactly $k$ components form the $k$ -fold labelled product $A^{⋆ k}$ , with EGF $A^{k}$ by the EGF product rule and induction. Since $a_{0} = 0$ we have $ord (A) \geq 1$ , so $(A^{k})_{k \geq 0}$ is summable and, exactly as in the ordinary Sequence Construction theorem, $\sum_{k \geq 0} A^{k} = \frac{1}{1 - A}$ .

(2) A set of $k$ components is an ordered $k$ -tuple of components with the ordering forgotten. The $k$ components occupy disjoint, non-empty blocks of labels, so they are pairwise distinct as (block, structure) pairs, and each set of $k$ components arises from exactly $k!$ of the ordered tuples. Hence the EGF for sets of exactly $k$ components is $\frac{A ^{k}}{k !}$ — division by the integer $k!$ is legitimate since we work over $Q$ — and summing over $k \geq 0$ gives $\sum_{k \geq 0} \frac{A ^{k}}{k !} = exp (A)$ , the family again being summable.

(3) A cyclic arrangement of $k$ components is an ordered $k$ -tuple up to cyclic rotation, and the $k$ rotations of a tuple of $k$ distinct components are distinct, so the EGF for $k$ -cycles of components is $\frac{A ^{k}}{k}$ for $k \geq 1$ . Summing, $\sum_{k \geq 1} \frac{A ^{k}}{k} = ln \frac{1}{1 - A}$ , by the definition of the logarithm series.∎

Corollary 3.39 (Cycles of atoms). The number of ways to arrange $n$ labelled elements ( $n \geq 1$ ) in a single cycle is $(n - 1)!$ , and the EGF of cyclic arrangements is $ln \frac{1}{1 - x}$ .

Proof. Take $A$ to be the class of single atoms, $A (x) = x$ ; part (3) of the constructions theorem gives $ln \frac{1}{1 - x} = \sum_{k \geq 1} \frac{x ^{k}}{k}$ . The count is therefore $n! [x^{n}] ln \frac{1}{1 - x} = \frac{n !}{n} = (n - 1)!$ , in agreement with the direct argument that a cycle on $n$ elements is one of the $n!$ linear orders, with each cycle arising from exactly $n$ of them.∎

Theorem 3.40 (The exponential formula). Let $C$ be a labelled class of "connected" structures with $c_{0} = 0$ and EGF $C (x)$ , and let $A$ be the class whose structures on $U$ are the ways of partitioning $U$ into non-empty blocks and placing a $C$ -structure on each block. Then

A (x) = exp (C (x)) .

Equivalently, in coefficients,

a_{n} = k \geq 0 \sum \frac{1}{k !} n_{1} + \dots + n_{k} = n n_{i} \geq 1 \sum (n _{1} , \dots , n _{k} n) c_{n_{1}} \dots c_{n_{k}} .

Proof. This is part (2) of the constructions theorem applied to $A = SET (C)$ ; the coefficient form is obtained by expanding $exp (C) = \sum_{k} \frac{C ^{k}}{k !}$ and reading off $n! [x^{n}]$ of the $k$ -th term, the multinomial coefficient being the number of ways to distribute the $n$ labels into the ordered blocks of sizes $n_{1}, \dots, n_{k}$ .∎

Intuition. The exponential formula says: if you know how to count the connected pieces, exponentiating counts everything. Graphs are the archetype — every graph is a set of connected graphs on the blocks of a partition of its vertices — and the same sentence covers permutations (a permutation is a set of cycles), set partitions (a partition is a set of blocks), and forests (a forest is a set of trees). Nothing in the proof knows what "connected" means; it only needs that every structure decomposes uniquely into pieces sitting on the blocks of a partition.

Read in the other direction, the formula is equally useful: $C = ln A$ defines the connected count from the total count, which is how one counts connected labelled graphs.

Example 3.41 (Permutations as sets of cycles). Derive the EGF of permutations from the exponential formula, and confirm it against the direct count.

Solution. Every permutation of a finite set decomposes uniquely into cycles, and the cycles sit on the blocks of a partition of the label set — so permutations are $SET (cycles)$ . By the cycles corollary the cycle EGF is $ln \frac{1}{1 - x}$ , so

P (x) = exp (ln \frac{1}{1 - x}) = \frac{1}{1 - x},

whose $n$ -th count is $n! [x^{n}] \frac{1}{1 - x} = n!$ . Correct, and derived rather than assumed.□

Example 3.42 (Set partitions and the Bell numbers). Find the EGF of the Bell numbers $B_{n}$ (the number of partitions of an $n$ -set into non-empty blocks), and use it to prove the recurrence $B_{n + 1} = \sum_{k = 0}^{n} (k n) B_{k}$ .

Solution. A block is a non-empty set of labels with no further structure, one structure per non-empty label set, so the block EGF is $e^{x} - 1$ (the $- 1$ removing the empty block). A partition is a set of blocks, so by the exponential formula

B (x) = exp (e^{x} - 1) .

Differentiate, using the formal chain rule: $B^{'} (x) = e^{x} exp (e^{x} - 1) = e^{x} B (x)$ . By part (1) of the EGF dictionary, $B^{'}$ is the EGF of $(B_{n + 1})$ , and by the EGF product rule the right-hand side is the binomial convolution of the sequence $1, 1, 1, \dots$ (EGF $e^{x}$ ) with $(B_{k})$ . Comparing coefficients of $\frac{x ^{n}}{n !}$ :

B_{n + 1} = k = 0 \sum n (k n) \cdot 1 \cdot B_{k} .

From $B_{0} = 1$ this gives $B_{1} = 1$ , $B_{2} = 2$ , $B_{3} = 5$ , $B_{4} = 15$ , $B_{5} = 52$ .

The combinatorial reading of the recurrence is also worth having: in a partition of $[n + 1]$ , look at the block containing $n + 1$ ; it contains $n - k$ of the other elements for some $k$ , chosen in $(n - k n) = (k n)$ ways, and the remaining $k$ elements are partitioned in $B_{k}$ ways.□

Example 3.43 (Stirling numbers of the second kind). Let $S (n, k)$ be the number of partitions of $[n]$ into exactly $k$ non-empty blocks. Find $\sum_{n} S (n, k) \frac{x ^{n}}{n !}$ and deduce the explicit formula.

Solution. Partitions into exactly $k$ blocks are sets of exactly $k$ blocks, so by the proof of the constructions theorem the EGF is

n \geq 0 \sum S (n, k) \frac{x ^{n}}{n !} = \frac{( e ^{x} - 1 ) ^{k}}{k !} .

Expand the $k$ -th power with the ordinary binomial theorem:

\frac{( e ^{x} - 1 ) ^{k}}{k !} = \frac{1}{k !} j = 0 \sum k (j k) (- 1)^{k - j} e^{j x},

and $n! [x^{n}] e^{j x} = j^{n}$ . Therefore

S (n, k) = \frac{1}{k !} j = 0 \sum k (- 1)^{k - j} (j k) j^{n},

which is the inclusion–exclusion formula for surjections divided by $k!$ — as it must be, since a partition into $k$ labelled blocks is a surjection $[n] \to [k]$ and forgetting the block labels divides by $k!$ .

Check: $S (4, 2) = \frac{1}{2} ((1 2) (- 1)^{1} 1^{4} + (2 2) 2^{4}) = \frac{1}{2} (- 2 + 16) = 7$ , and indeed $B_{4} = S (4, 1) + S (4, 2) + S (4, 3) + S (4, 4) = 1 + 7 + 6 + 1 = 15$ .□

Example 3.44 (Involutions). An involution of $[n]$ is a permutation $σ$ with $σ^{2} = id$ . Find the EGF of the number $I_{n}$ of involutions and the recurrence it satisfies.

Solution. A permutation is an involution exactly when all its cycles have length $1$ or $2$ . The class of such cycles has EGF $x + \frac{x ^{2}}{2}$ (one fixed point per singleton; one transposition per pair, and $\frac{2 !}{2} = 1$ agrees with $2! [x^{2}] \frac{x ^{2}}{2} = 1$ ). By the exponential formula,

I (x) = exp (x + \frac{x ^{2}}{2}) .

Differentiating, $I^{'} (x) = (1 + x) I (x)$ . The left side is the EGF of $(I_{n + 1})$ ; the right side is the EGF of $I_{n} + n I_{n - 1}$ by parts (1) and (2) of the EGF dictionary. Hence

I_{n + 1} = I_{n} + n I_{n - 1},

with $I_{0} = I_{1} = 1$ , giving $1, 1, 2, 4, 10, 26, 76, \dots$ . The combinatorial reading: either $n + 1$ is fixed, or it is paired with one of the $n$ other elements.□

Exercises for §3.5 →

3.6Choosing Between OGFs and EGFs

The two bookkeepings are two ways of storing the same sequence, so neither carries more information than the other. The difference is entirely in which constructions become clean algebra.

Proposition 3.45 (The two bookkeepings compared). Let $A, B$ be classes and $C$ a class built from them. Then:

construction	OGF	EGF
disjoint union	$A + B$	$A + B$
product (split the size / split the labels)	$A B$	$A B$
sequence of components	$\frac{1}{1 - A}$	$\frac{1}{1 - A}$
set / multiset of components	$exp (\sum_{k \geq 1} \frac{A ( x ^{k} )}{k})$	$exp (A)$
cycle of components	$\sum_{k \geq 1} \frac{φ ( k )}{k} ln \frac{1}{1 - A ( x ^{k} )}$	$ln \frac{1}{1 - A}$

In both columns the sequence, set and cycle rows require the component class to have no object of size $0$ .

Proof. The union, product and sequence rows are the Product Rule, the Sequence Construction theorem and their EGF counterparts. The set row in the EGF column is part (2) of the constructions theorem. We prove the multiset row in the OGF column, which is the one genuinely new statement; the unlabelled cycle row (Pólya's cycle-index computation, using Euler's totient $φ$ ) is proved the same way and we state it without carrying out the details.

A multiset of $A$ -objects records, for each object $α \in A$ , a multiplicity $m_{α} \geq 0$ , with only finitely many non-zero. The size is $\sum_{α} m_{α} ∣ α ∣$ , so, by the same expansion used for Euler's Product Formula,

M (x) = α \in A \prod \frac{1}{1 - x ^{∣ α ∣}} = n \geq 1 \prod (\frac{1}{1 - x ^{n}})^{a_{n}},

the product being well defined because $a_{0} = 0$ makes every factor of order at least $1$ . Now take formal logarithms — legitimate since each factor has constant term $1$ — and use $ln \frac{1}{1 - y} = \sum_{k \geq 1} \frac{y ^{k}}{k}$ :

ln M (x) = n \geq 1 \sum a_{n} k \geq 1 \sum \frac{x ^{nk}}{k} = k \geq 1 \sum \frac{1}{k} n \geq 1 \sum a_{n} (x^{k})^{n} = k \geq 1 \sum \frac{A ( x ^{k} )}{k},

the interchange being valid coefficientwise (for a fixed power of $x$ , only finitely many pairs $(n, k)$ contribute). Exponentiating gives the stated formula.∎

Intuition. Look at the two "set" rows. In the labelled world, $exp (A)$ — one clean exponential. In the unlabelled world, $exp (A (x) + \frac{A ( x ^{2} )}{2} + \frac{A ( x ^{3} )}{3} + \dots)$ , the extra terms compensating for repeated components, which in the labelled world can never occur because distinct components carry distinct labels. That asymmetry is the whole reason for having two theories. Labels break symmetry, and broken symmetry is what makes the algebra simple.

The practical rule. If the objects are built on distinguishable atoms and the construction involves distributing those atoms, use an EGF. If the objects are anonymous and the construction involves distributing size, use an OGF.

Proposition 3.46 (When labelling is free). Suppose every object of size $n$ in a labelled class $A$ has trivial symmetry — that is, no non-identity relabelling of $[n]$ fixes it. Then the number $\tilde{a}_{n}$ of unlabelled objects (relabelling classes) of size $n$ satisfies $a_{n} = n! \tilde{a}_{n}$ , so $A (x)$ is the OGF of $(\tilde{a}_{n})$ .

Proof. Relabelling acts on $A [[n]]$ ; two structures are the same unlabelled object exactly when they lie in the same orbit. By the orbit–stabiliser theorem every orbit has size $n! /∣ stabiliser ∣ = n!$ under the triviality hypothesis, so the $a_{n}$ structures fall into $a_{n} / n!$ orbits.∎

Example 3.47 (Derangements). A derangement is a permutation with no fixed point. Find the EGF of the number $d_{n}$ of derangements of $[n]$ and the closed form, then evaluate $d_{4}$ .

Solution. A derangement is a permutation all of whose cycles have length at least $2$ . Deleting the length- $1$ term $x$ from the cycle EGF $ln \frac{1}{1 - x} = \sum_{k \geq 1} \frac{x ^{k}}{k}$ leaves $ln \frac{1}{1 - x} - x$ , so by the exponential formula

D (x) = exp (ln \frac{1}{1 - x} - x) = \frac{e ^{- x}}{1 - x} .

Extract the coefficient by the Cauchy product, using $e^{- x} = \sum_{j} \frac{( - 1 ) ^{j}}{j !} x^{j}$ and $\frac{1}{1 - x} = \sum_{i} x^{i}$ :

[x^{n}] D (x) = j = 0 \sum n \frac{( - 1 ) ^{j}}{j !}, so d_{n} = n! j = 0 \sum n \frac{( - 1 ) ^{j}}{j !} .

At $n = 4$ : $d_{4} = 24 (1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24}) = 24 \cdot \frac{9}{24} = 9$ .

The closed form is exactly what inclusion–exclusion over the set of fixed points gives, and the factor $e^{- x}$ is where the alternating signs came from: multiplying by $e^{- x}$ is the generating-function form of inclusion–exclusion on labelled structures.□

Remark (Sums with no closed form, and the transform between the two). The OGF of the derangement numbers is $\sum_{n} d_{n} x^{n}$ , and since $d_{n} \sim n! / e$ it converges nowhere but $0$ and has no elementary closed form. That is the general situation: for labelled classes the OGF is usually intractable and the EGF is usually clean, while for partitions and other unlabelled classes it is the reverse.

There is a transform between them — the Borel transform, in one direction the coefficientwise division by $n!$ , in the other the Laplace-type integral $A (x) = \int_{0}^{\infty} e^{- t} A (x t) d t$ — but the integral form is an analytic statement requiring convergence hypotheses we have deliberately avoided, and it is out of scope here. In practice one never converts; one chooses the right bookkeeping at the start.

Exercises for §3.6 →

3.7Linear Recurrences with Constant Coefficients

A recurrence defines a sequence by expressing each term in terms of earlier ones. Recurrences are how counting problems usually present themselves — condition on the last step, on the first return, on the block containing the largest element — and generating functions are how they get solved. The two halves of this chapter meet here.

Definition 3.48 (Linear recurrence with constant coefficients). A sequence $(a_{n})_{n \geq 0}$ satisfies a linear homogeneous recurrence with constant coefficients of order $d$ if there are constants $c_{1}, \dots, c_{d}$ with $c_{d} \neq = 0$ such that

a_{n} = c_{1} a_{n - 1} + c_{2} a_{n - 2} + \dots + c_{d} a_{n - d} for all n \geq d .

"Linear" means each $a_{n - i}$ occurs to the first power with no products between terms; "homogeneous" means there is no extra additive term. The values $a_{0}, \dots, a_{d - 1}$ are the initial conditions, and together with the recurrence they determine the sequence uniquely.

The single fact from which everything else follows is that such sequences are exactly the ones with a rational generating function.

Theorem 3.49 (Rationality). Let $Q (x) = 1 - c_{1} x - c_{2} x^{2} - \dots - c_{d} x^{d}$ and let $A (x)$ be the OGF of $(a_{n})$ . Then $(a_{n})$ satisfies the recurrence $a_{n} = \sum_{i = 1}^{d} c_{i} a_{n - i}$ for all $n \geq d$ if and only if

A (x) = \frac{P ( x )}{Q ( x )}

for some polynomial $P$ with $de g P < d$ . In that case $P (x) = A (x) Q (x)$ is determined by the initial conditions, namely

P (x) = n = 0 \sum d - 1 (a_{n} - i = 1 \sum n c_{i} a_{n - i}) x^{n} .

Proof. Compute the product $A (x) Q (x)$ coefficientwise. With the convention $a_{m} = 0$ for $m < 0$ ,

[x^{n}] A (x) Q (x) = a_{n} - i = 1 \sum d c_{i} a_{n - i} .

For $n \geq d$ this expression is precisely "left-hand side minus right-hand side" of the recurrence at index $n$ . Hence the recurrence holds for all $n \geq d$ if and only if every coefficient of $A Q$ in degree $\geq d$ vanishes, i.e. if and only if $A Q$ is a polynomial of degree $< d$ . Since $Q (0) = 1 \neq = 0$ , $Q$ is a unit (the Units Theorem), so $A Q = P$ may be rewritten as $A = P / Q$ . The displayed formula for $P$ is the same coefficient computation for $n < d$ , where the terms with negative index drop out.∎

Intuition. The theorem is a genuine equivalence, and both directions get used. Left to right: if you have a recurrence, you instantly have a closed-form rational generating function — no work, just read off $Q$ from the coefficients and $P$ from the initial conditions. Right to left: if a generating function turns out to be rational, its coefficients must satisfy a linear recurrence, and the denominator tells you which one. That is often the quickest way to prove a recurrence you would otherwise have to fight for combinatorially.

Extracting coefficients from $P / Q$ is then a matter of partial fractions, which is where the roots enter.

Theorem 3.50 (Partial fractions and the closed form). Let $A = P / Q$ with $de g P < d = de g Q$ and $Q (0) = 1$ . Factor $Q$ over $C$ as

Q (x) = i = 1 \prod s (1 - r_{i} x)^{m_{i}}, r_{i} distinct and non-zero, i \sum m_{i} = d .

Then there are constants $α_{i, j}$ with

A (x) = i = 1 \sum s j = 1 \sum m_{i} \frac{α _{i, j}}{( 1 - r _{i} x ) ^{j}},

and consequently

a_{n} = i = 1 \sum s p_{i} (n) r_{i}^{n}

where $p_{i}$ is a polynomial of degree at most $m_{i} - 1$ . Conversely every sequence of that shape satisfies the recurrence with denominator $Q$ .

Proof. The partial fraction decomposition of a rational function whose denominator factors as above is standard algebra over a field: the $\frac{1}{( 1 - r _{i} x ) ^{j}}$ for $1 \leq j \leq m_{i}$ , $1 \leq i \leq s$ , are $d$ elements spanning the $d$ -dimensional space of rational functions with denominator dividing $Q$ and numerator of degree $< d$ , and they are linearly independent, so they form a basis.

For the coefficients, the negative-exponent corollary applied with $r_{i} x$ in place of $x$ gives

\frac{1}{( 1 - r _{i} x ) ^{j}} = n \geq 0 \sum (j - 1 n + j - 1) r_{i}^{n} x^{n} .

Now $(j - 1 n + j - 1) = \frac{( n + 1 ) ( n + 2 ) \dots ( n + j - 1 )}{( j - 1 )!}$ is a polynomial in $n$ of degree exactly $j - 1$ . Summing over $j \leq m_{i}$ produces a polynomial $p_{i} (n)$ of degree at most $m_{i} - 1$ multiplying $r_{i}^{n}$ , as claimed. The converse follows because each such term has rational generating function with denominator $(1 - r_{i} x)^{m_{i}}$ , and the Rationality Theorem applies to the sum.∎

Remark (The characteristic equation). The characteristic polynomial of the recurrence is

χ (t) = t^{d} - c_{1} t^{d - 1} - \dots - c_{d},

and it is the reverse of $Q$ : $χ (t) = t^{d} Q (1/ t)$ . Hence $Q (x) = \prod_{i} (1 - r_{i} x)^{m_{i}}$ if and only if $χ (t) = \prod_{i} (t - r_{i})^{m_{i}}$ — the roots of the characteristic equation are exactly the reciprocals of the roots of $Q$ , and they are the $r_{i}$ appearing in the closed form. This recovers the familiar recipe: solve $χ (t) = 0$ ; for a simple root $r$ take a term $α r^{n}$ ; for a root of multiplicity $m$ take $(α_{0} + α_{1} n + \dots + α_{m - 1} n^{m - 1}) r^{n}$ ; fix the constants from the initial conditions. The generating-function proof explains why the polynomial factors appear for repeated roots — they come from $(j - 1 n + j - 1)$ — where the guess-and-verify derivation can only assert them.

Example 3.51 (Fibonacci in closed form). Let $F_{0} = 0$ , $F_{1} = 1$ and $F_{n} = F_{n - 1} + F_{n - 2}$ . Find the generating function and prove Binet's formula.

Solution. Generating function. Here $d = 2$ , $c_{1} = c_{2} = 1$ , so $Q (x) = 1 - x - x^{2}$ . By the Rationality Theorem, $P (x) = F_{0} + (F_{1} - F_{0}) x = x$ , so

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

Factor the denominator. If $1 - x - x^{2} = (1 - φ x) (1 - ψ x)$ then expanding gives $φ + ψ = 1$ and $φ ψ = - 1$ , so $φ, ψ$ are the roots of $t^{2} - t - 1 = 0$ :

φ = \frac{1 + 5}{2}, ψ = \frac{1 - 5}{2}, φ - ψ = 5 .

(As predicted by the characteristic-equation remark, $t^{2} - t - 1$ is the reverse of $1 - x - x^{2}$ .)

Partial fractions. Since

\frac{1}{1 - φ x} - \frac{1}{1 - ψ x} = \frac{( 1 - ψ x ) - ( 1 - φ x )}{( 1 - φ x ) ( 1 - ψ x )} = \frac{( φ - ψ ) x}{1 - x - x ^{2}},

we get

F (x) = \frac{1}{5} (\frac{1}{1 - φ x} - \frac{1}{1 - ψ x}) .

Extract. By the geometric series identity, $[x^{n}] \frac{1}{1 - φ x} = φ^{n}$ , so

F_{n} = \frac{φ ^{n} - ψ ^{n}}{5} .

Check. $F_{2} = \frac{φ ^{2} - ψ ^{2}}{5} = \frac{( φ + ψ ) ( φ - ψ )}{5} = \frac{1 \cdot 5}{5} = 1$ , and $F_{5} = \frac{11.0902 \dots - ( - 0.0902 \dots )}{2.2360 \dots} = 5$ . Both correct.

Note what the formula says: $∣ ψ ∣ = 0.618 \dots < 1$ , so $ψ^{n} \to 0$ and $F_{n}$ is the nearest integer to $φ^{n} / 5$ — an exact statement about growth extracted from the position of the smallest root of the denominator, which is the first hint of how singularities govern asymptotics.□

Figure 3.52. Successive ratios

F_{n + 1} / F_{n}

alternate around

φ

and close in on it, because the closed form carries a second term in

ψ^{n}

with

∣ ψ ∣ < 1

Example 3.53 (A repeated root). Solve $a_{n} = 4 a_{n - 1} - 4 a_{n - 2}$ with $a_{0} = 1$ , $a_{1} = 3$ .

Solution. $Q (x) = 1 - 4 x + 4 x^{2} = (1 - 2 x)^{2}$ , a double root $r = 2$ . By the Rationality Theorem, $P (x) = a_{0} + (a_{1} - 4 a_{0}) x = 1 - x$ , so

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

Write $1 - x = α (1 - 2 x) + β$ . Matching the $x$ terms gives $- 2 α = - 1$ , so $α = \frac{1}{2}$ ; matching constants gives $α + β = 1$ , so $β = \frac{1}{2}$ . Hence

A (x) = \frac{1/2}{1 - 2 x} + \frac{1/2}{( 1 - 2 x ) ^{2}},

and by the negative-exponent corollary,

a_{n} = \frac{1}{2} \cdot 2^{n} + \frac{1}{2} (n + 1) 2^{n} = (n + 2) 2^{n - 1} .

Check. $a_{0} = 2 \cdot \frac{1}{2} = 1$ ; $a_{1} = 3 \cdot 1 = 3$ ; $a_{2} = 4 \cdot 2 = 8$ , and the recurrence gives $4 \cdot 3 - 4 \cdot 1 = 8$ . The linear factor $n$ in the answer is exactly the $(1 n + 1)$ from the squared denominator.□

Example 3.54 (Pell numbers). Solve $a_{n} = 2 a_{n - 1} + a_{n - 2}$ with $a_{0} = 0$ , $a_{1} = 1$ .

Solution. $Q (x) = 1 - 2 x - x^{2}$ and $P (x) = a_{0} + (a_{1} - 2 a_{0}) x = x$ , so $A (x) = \frac{x}{1 - 2 x - x ^{2}}$ . The characteristic polynomial $t^{2} - 2 t - 1$ has roots $r_{\pm} = 1 \pm 2$ , with $r_{+} - r_{-} = 22$ , so the same partial-fraction computation as for Fibonacci gives

a_{n} = \frac{( 1 + 2 ) ^{n} - ( 1 - 2 ) ^{n}}{2 2} .

Check. $a_{2} = \frac{( 3 + 2 2 ) - ( 3 - 2 2 )}{2 2} = \frac{4 2}{2 2} = 2$ , matching $2 a_{1} + a_{0} = 2$ . Also $a_{3} = 2 \cdot 2 + 1 = 5$ .□

Theorem 3.55 (Inhomogeneous recurrences). Suppose $a_{n} = \sum_{i = 1}^{d} c_{i} a_{n - i} + g_{n}$ for $n \geq d$ , where $(g_{n})$ has OGF $G (x)$ . Then, with $Q$ and $P$ as in the Rationality Theorem,

A (x) = \frac{P ( x ) + G ^{\geq d} ( x )}{Q ( x )},

where $G^{\geq d} (x) = \sum_{n \geq d} g_{n} x^{n}$ . In particular, if $G$ is rational then so is $A$ , and the closed form is again a sum of terms $p (n) r^{n}$ — now including the roots contributed by the denominator of $G$ .

Proof. The computation in the Rationality Theorem proof now gives $[x^{n}] (A Q) = g_{n}$ for $n \geq d$ and the same initial data below $d$ , so $A Q = P + G^{\geq d}$ ; divide by the unit $Q$ .∎

Example 3.56 (Doubling with an increment). Solve $a_{n} = 2 a_{n - 1} + 1$ for $n \geq 1$ , with $a_{0} = 0$ . (This is the Tower of Hanoi recurrence.)

Solution. Here $d = 1$ , $Q (x) = 1 - 2 x$ , $P (x) = a_{0} = 0$ , and $g_{n} = 1$ for $n \geq 1$ , so $G^{\geq 1} (x) = \frac{x}{1 - x}$ . By the inhomogeneous theorem,

A (x) = \frac{x}{( 1 - x ) ( 1 - 2 x )} .

Partial fractions: write $\frac{x}{( 1 - x ) ( 1 - 2 x )} = \frac{α}{1 - x} + \frac{β}{1 - 2 x}$ , i.e. $x = α (1 - 2 x) + β (1 - x)$ . Setting $x = 1$ gives $1 = - α$ , so $α = - 1$ ; setting $x = \frac{1}{2}$ gives $\frac{1}{2} = \frac{1}{2} β$ , so $β = 1$ . Hence

a_{n} = 2^{n} - 1.

Check. $a_{0} = 0$ , $a_{1} = 1$ , $a_{2} = 3$ , $a_{3} = 7$ ; and $2 \cdot 3 + 1 = 7$ . The extra root $r = 1$ in the closed form came entirely from the denominator of the forcing term's generating function, exactly as the theorem predicts.□

Exercises for §3.7 →

3.8Combinatorial Recurrences and Functional Equations

Not every recurrence that arises from counting is linear with constant coefficients. Two other shapes are common: convolution recurrences, in which the terms multiply two earlier values, and recurrences with polynomial coefficients. Generating functions handle both — the first by producing an algebraic equation, the second by producing a differential equation.

Definition 3.57 (Catalan numbers). $C_{n}$ is the number of balanced strings of $n$ pairs of parentheses (equivalently: binary trees with $n$ internal nodes; triangulations of a convex $(n + 2)$ -gon; lattice paths from $(0, 0)$ to $(n, n)$ by unit right and up steps that never rise above the diagonal). By convention $C_{0} = 1$ , the empty string.

Proposition 3.58 (The Catalan recurrence). For $n \geq 1$ ,

C_{n} = k = 0 \sum n - 1 C_{k} C_{n - 1 - k} .

Proof. Let $w$ be a non-empty balanced string. Its first character is an opening parenthesis; let its matching closing parenthesis be at position $2 k + 2$ . Then $w$ factors uniquely as $w = (u) v$ where $u$ is the (balanced) substring strictly inside the matching pair, with $k$ pairs, and $v$ is the balanced remainder, with $n - 1 - k$ pairs. The factorisation is unique because the matching partner of the first character is determined by $w$ ; conversely, every choice of $k$ , $u$ and $v$ produces a distinct balanced string with $n$ pairs. Summing over $k$ from $0$ to $n - 1$ gives the identity.∎

Figure 3.59. The first-return decomposition of a Dyck path. The opening step and the step on which the path first returns to the axis are highlighted; between them lies a Dyck path

u

, and after them a Dyck path

v

, with

∣ u ∣ + ∣ v ∣ = n - 1

Theorem 3.60 (The Catalan generating function). $C (x) = \sum_{n \geq 0} C_{n} x^{n}$ satisfies the functional equation $C (x) = 1 + x C (x)^{2}$ , and

C (x) = \frac{1 - 1 - 4 x}{2 x}, C_{n} = \frac{1}{n + 1} (n 2 n) .

Here $1 - 4 x := (1 + y)^{1/2}_{y = - 4 x}$ in the sense of the generalised binomial theorem.

Proof. The functional equation. By the Product Rule, $[x^{n - 1}] C (x)^{2} = \sum_{k = 0}^{n - 1} C_{k} C_{n - 1 - k}$ , which by the Catalan recurrence is $C_{n}$ for $n \geq 1$ . So $x C (x)^{2}$ and $C (x)$ agree in every degree $n \geq 1$ , and they differ in degree $0$ by $C_{0} = 1$ . Hence $C = 1 + x C^{2}$ .

Solving. Write $S = (1 - 4 x)^{1/2}$ . By the generalised binomial theorem with $α = β = \frac{1}{2}$ we have $S^{2} = (1 - 4 x)^{1} = 1 - 4 x$ ; the substitution $y = - 4 x$ is legitimate since $y$ has zero constant term. Regard $C = 1 + x C^{2}$ as a quadratic: $x C^{2} - C + 1 = 0$ , so

(2 x C - 1)^{2} = 1 - 4 x = S^{2},

as one checks by expanding: $(2 x C - 1)^{2} = 4 x^{2} C^{2} - 4 x C + 1 = 4 x (x C^{2} - C) + 1 = 4 x (- 1) + 1$ . Since $K [[x]]$ is an integral domain, $(2 x C - 1 - S) (2 x C - 1 + S) = 0$ forces $2 x C - 1 = \pm S$ . Comparing constant terms: $2 x C - 1$ has constant term $- 1$ , while $S$ has constant term $+ 1$ . So the sign must be $-$ , giving $2 x C = 1 - S$ and

C (x) = \frac{1 - 1 - 4 x}{2 x},

a legitimate power series because $1 - S$ has zero constant term and is therefore divisible by $x$ in $K [[x]]$ .

Coefficients. By the definition of $(1 + x)^{α}$ ,

S = n \geq 0 \sum (n 1/2) (- 4)^{n} x^{n} .

For $n \geq 1$ compute the coefficient. The numerator of $(n 1/2)$ is a product of $n$ halves,

\frac{1}{2} (\frac{1}{2} - 1) \dots (\frac{1}{2} - n + 1) = \frac{1 \cdot ( - 1 ) \cdot ( - 3 ) \dots ( 3 - 2 n )}{2 ^{n}} = \frac{( - 1 ) ^{n - 1} 1 \cdot 3 \cdot 5 \dots ( 2 n - 3 )}{2 ^{n}},

so, using $(- 4)^{n} = (- 1)^{n} 4^{n}$ and $(- 1)^{n} (- 1)^{n - 1} = - 1$ ,

(n 1/2) (- 4)^{n} = - \frac{4 ^{n}}{2 ^{n} n !} 1 \cdot 3 \cdot 5 \dots (2 n - 3) = - \frac{2 ^{n}}{n !} 1 \cdot 3 \dots (2 n - 3) .

Complete the odd product to a factorial using $1 \cdot 3 \dots (2 n - 3) = \frac{( 2 n - 2 )!}{2 ^{n - 1} ( n - 1 )!}$ :

(n 1/2) (- 4)^{n} = - \frac{2 ^{n}}{n !} \cdot \frac{( 2 n - 2 )!}{2 ^{n - 1} ( n - 1 )!} = - \frac{2 ( 2 n - 2 )!}{n ! ( n - 1 )!} = - \frac{2}{n} (n - 1 2 n - 2) .

(Sanity check at small $n$ : $n = 1$ gives $- 2 (0 0) = - 2$ , and directly $(1 1/2) (- 4) = - 2$ ; $n = 2$ gives $- (1 2) = - 2$ , and directly $- \frac{1}{8} \cdot 16 = - 2$ ; $n = 3$ gives $- \frac{2}{3} (2 4) = - 4$ , and directly $\frac{1}{16} \cdot (- 64) = - 4$ .)

Hence $S = 1 - \sum_{n \geq 1} \frac{2}{n} (n - 1 2 n - 2) x^{n}$ , and

C (x) = \frac{1 - S}{2 x} = \frac{1}{2 x} n \geq 1 \sum \frac{2}{n} (n - 1 2 n - 2) x^{n} = n \geq 1 \sum \frac{1}{n} (n - 1 2 n - 2) x^{n - 1} = m \geq 0 \sum \frac{1}{m + 1} (m 2 m) x^{m} .

So $C_{m} = \frac{1}{m + 1} (m 2 m)$ , which for $m = 0, 1, 2, 3, 4, 5$ gives $1, 1, 2, 5, 14, 42$ — matching the recurrence.∎

Pitfall (Choosing the wrong branch). The quadratic formula offers two roots, and only one of them is a formal power series. The test is always the constant term: $C (0) = C_{0}$ must be finite and correct, whereas $\frac{1 + 1 - 4 x}{2 x}$ has a numerator with constant term $2$ , so it is not divisible by $x$ and is not an element of $K [[x]]$ at all. Never choose the branch by plugging in a small number and seeing which "looks right" — check the order of the numerator.

Intuition. Look at what the functional equation $C = 1 + x C^{2}$ says: a balanced string is either empty, or it is a pair of parentheses (the $x$ , contributing size $1$ ) wrapping one balanced string, followed by another balanced string. The equation is the decomposition, transcribed. Deriving the recurrence first and then the equation, as we did, is the careful route; with practice one writes the functional equation directly from the decomposition and never mentions the recurrence at all.

Example 3.61 (Motzkin numbers). $M_{n}$ counts lattice paths from $(0, 0)$ to $(n, 0)$ using steps $U = (1, 1)$ , $D = (1, - 1)$ and $L = (1, 0)$ that never go below the horizontal axis. Find the functional equation for $M (x)$ .

Solution. Decompose a non-empty path by its first step. If it is $L$ , the rest is an arbitrary Motzkin path of length $n - 1$ , contributing $x M (x)$ . If it is $U$ , the path must return to the axis for the first time by some $D$ step; between them lies a Motzkin path (shifted up by one), and after the $D$ lies another Motzkin path. That contributes $x^{2} M (x)^{2}$ , the $x^{2}$ accounting for the $U$ and the $D$ . The decomposition is unambiguous, so

M (x) = 1 + x M (x) + x^{2} M (x)^{2} .

Solving as before (and taking the branch with the correct constant term) gives

M (x) = \frac{1 - x - 1 - 2 x - 3 x ^{2}}{2 x ^{2}},

whose coefficients begin $1, 1, 2, 4, 9, 21, 51$ . Equating coefficients in the functional equation instead gives the recurrence $M_{n} = M_{n - 1} + \sum_{k = 0}^{n - 2} M_{k} M_{n - 2 - k}$ , which is the fastest way to tabulate them.□

Theorem 3.62 (Recurrences with polynomial coefficients). If a sequence satisfies a recurrence whose coefficients are polynomials in $n$ , its generating function satisfies a linear differential equation with polynomial coefficients, obtained by translating $n a_{n} \mapsto x A^{'} (x)$ and $a_{n - 1} \mapsto$ a shift. Sequences of this kind are called holonomic (or $P$ -recursive), and the differential equation is often solvable in closed form even when the recurrence is not.

Proof. Each occurrence of $a_{n - i}$ contributes $x^{i} A (x)$ up to finitely many initial terms (the shift rule), and each factor of $n$ multiplying a coefficient contributes the operator $x \frac{d}{d x}$ (part 6 of the Dictionary of Coefficient Operations). Since the recurrence is a finite linear combination of such terms with polynomial coefficients, the result is a finite linear combination of $A$ , $A^{'}$ , $A^{''}$ , … with polynomial coefficients equated to a polynomial. That the operator translation is valid is exactly the two dictionary entries; no convergence is involved because the formal derivative is defined coefficientwise.∎

Example 3.63 (Involutions again, from the recurrence). Solve $I_{n + 1} = I_{n} + n I_{n - 1}$ , $I_{0} = I_{1} = 1$ , using an exponential generating function.

Solution. Let $I (x) = \sum_{n} I_{n} \frac{x ^{n}}{n !}$ . Setting $I_{- 1} := 0$ makes the recurrence valid for every $n \geq 0$ , since at $n = 0$ it reads $I_{1} = I_{0} + 0$ . Multiply by $\frac{x ^{n}}{n !}$ and sum over $n \geq 0$ : by part (1) of the EGF dictionary the left side is the EGF of $(I_{n + 1})$ , namely $I^{'}$ ; the first term on the right is $I$ ; and by part (2) the term $n I_{n - 1}$ has EGF $x I$ . So

I^{'} (x) = (1 + x) I (x) .

This is a first-order linear differential equation in $Q [[x]]$ . Writing $I = exp (H)$ with $H (0) = 0$ — legitimate since $I$ has constant term $I_{0} = 1$ — the formal chain rule turns it into $H^{'} = 1 + x$ , so $H = x + \frac{x ^{2}}{2}$ and

I (x) = exp (x + \frac{x ^{2}}{2}),

confirming the exponential-formula derivation from the labelled-structures section by a completely different route. Expanding to order $4$ : $exp (x + \frac{x ^{2}}{2}) = 1 + x + x^{2} + \frac{2 x ^{3}}{3} + \frac{5 x ^{4}}{12} + \dots$ , and multiplying by $n!$ gives $I_{0}, \dots, I_{4} = 1, 1, 2, 4, 10$ , as before.□

Remark (When the answer is not a closed form). It would be misleading to suggest every combinatorial recurrence yields a formula. The partition numbers $p (n)$ satisfy no linear recurrence with constant coefficients (their generating function is not rational — it has infinitely many singularities on the unit circle), and their exact asymptotic $p (n) \sim \frac{1}{4 n 3} exp (π 2 n /3)$ is the Hardy–Ramanujan theorem, proved by the circle method and far beyond this chapter. What a generating function reliably buys is a finite description of the whole sequence, plus the machinery to compute any term. A closed form is a bonus that appears when the series turns out to be rational or algebraic.

Exercises for §3.8 →

3.9Method: Solving Recurrences by Generating Function

This section gathers the methods into procedures, and adds two techniques that do not follow from the dictionary alone.

Method 3.64 (Solving a recurrence with an ordinary generating function).

Decide the range of $n$ for which the recurrence is valid, and set $a_{m} = 0$ for $m < 0$ if that makes it valid further down.
Multiply the recurrence by $x^{n}$ and sum over that range.
Rewrite each sum in terms of $A (x)$ using the shift rules, being careful about the finitely many initial terms that the shift adds or removes.
Solve the resulting equation for $A (x)$ — linear if the recurrence was linear, quadratic if it was a convolution.
Extract coefficients: partial fractions for rational $A$ , the generalised binomial theorem for algebraic $A$ , a convolution if $A$ is a product of two known series.
Verify the first three or four coefficients against a direct count.

Method 3.65 (Solving a recurrence with an exponential generating function). Use this when the recurrence contains binomial coefficients $(k n)$ in a convolution, or polynomial factors in $n$ .

Multiply by $\frac{x ^{n}}{n !}$ and sum.
Translate: $a_{n + 1} \mapsto A^{'}$ , $n a_{n - 1} \mapsto x A$ , $\sum_{k} (k n) a_{k} b_{n - k} \mapsto A B$ .
Solve the resulting differential equation; first-order linear equations are solved by the formal substitution $A = exp (H)$ when $A (0) = 1$ .
Recover $a_{n} = n! [x^{n}] A (x)$ .

Example 3.66 (A recurrence needing care with initial terms). Let $a_{0} = 1$ , $a_{1} = 1$ and $a_{n} = a_{n - 1} + a_{n - 2}$ for $n \geq 2$ . Derive $A (x)$ from scratch.

Solution. Multiply by $x^{n}$ and sum over $n \geq 2$ :

n \geq 2 \sum a_{n} x^{n} = n \geq 2 \sum a_{n - 1} x^{n} + n \geq 2 \sum a_{n - 2} x^{n} .

The left side is $A (x) - a_{0} - a_{1} x = A (x) - 1 - x$ . Reindexing the right-hand sums with $m = n - 1$ and $m = n - 2$ ,

n \geq 2 \sum a_{n - 1} x^{n} = x m \geq 1 \sum a_{m} x^{m} = x (A (x) - 1), n \geq 2 \sum a_{n - 2} x^{n} = x^{2} A (x) .

Hence $A - 1 - x = x A - x + x^{2} A$ ; the $- x$ terms cancel and

A (x) (1 - x - x^{2}) = 1, A (x) = \frac{1}{1 - x - x ^{2}} .

Compare with the Rationality Theorem, which gives the same answer in one line: $Q = 1 - x - x^{2}$ and $P = a_{0} + (a_{1} - a_{0}) x = 1$ . The point of doing it by hand once is step 3 — the term $x (A - 1)$ , not $x A$ — which is where sign and off-by-one errors live.

Since $\frac{1}{1 - x - x ^{2}} = \frac{1}{x} \cdot \frac{x}{1 - x - x ^{2}}$ , the Fibonacci computation gives $a_{n} = F_{n + 1} = \frac{φ ^{n + 1} - ψ ^{n + 1}}{5}$ .□

Theorem 3.67 (Lagrange inversion). Let $ϕ \in K [[t]]$ with $ϕ (0) \neq = 0$ . Then there is a unique $F \in K [[x]]$ with $F (0) = 0$ satisfying $F = x ϕ (F)$ , and for $n \geq 1$

[x^{n}] F (x) = \frac{1}{n} [t^{n - 1}] ϕ (t)^{n}, more generally [x^{n}] H (F (x)) = \frac{1}{n} [t^{n - 1}] (H^{'} (t) ϕ (t)^{n})

for any $H \in K [[t]]$ .

Proof. We do not prove this here. The standard proof runs through the formal residue $res (A) = [t^{- 1}] A$ on formal Laurent series, together with the two facts that $res (A^{'}) = 0$ for every formal Laurent series $A$ and that residues transform correctly under a change of variable of positive order; it is a page of careful bookkeeping and is carried out in Stanley's Enumerative Combinatorics and in Wilf's generatingfunctionology. We use the statement as a black box. Existence and uniqueness of $F$ , by contrast, is the same coefficient-by-coefficient recursion as in the Units Theorem.∎

Example 3.68 (Cayley's formula for labelled rooted trees). Let $T_{n}$ be the number of rooted trees on the labelled vertex set $[n]$ . Use Lagrange inversion to show $T_{n} = n^{n - 1}$ .

Solution. Specify. A rooted labelled tree is a root vertex together with a set of rooted labelled subtrees hanging from it, the subtrees sitting on the blocks of a partition of the remaining labels. By the exponential formula and the labelled product rule, the EGF $T$ satisfies

T (x) = x exp (T (x)),

the factor $x$ being the root atom.

Invert. This is $F = x ϕ (F)$ with $ϕ (t) = e^{t}$ , which has $ϕ (0) = 1 \neq = 0$ . Lagrange inversion gives, for $n \geq 1$ ,

[x^{n}] T (x) = \frac{1}{n} [t^{n - 1}] e^{n t} = \frac{1}{n} \cdot \frac{n ^{n - 1}}{( n - 1 )!} .

Recover the count.

T_{n} = n! [x^{n}] T (x) = \frac{n !}{n} \cdot \frac{n ^{n - 1}}{( n - 1 )!} = n^{n - 1} .

Check. $T_{1} = 1$ , $T_{2} = 2$ (either vertex may be the root), $T_{3} = 9$ : three choices of root times three unrooted trees on $3$ labelled vertices... more carefully, there are $3$ unrooted labelled trees on $[3]$ (the three paths) and $3$ choices of root, giving $9$ . Dividing $T_{n}$ by $n$ gives Cayley's formula $n^{n - 2}$ for unrooted labelled trees.□

The last technique goes the other way round: it uses generating functions to evaluate a sum, by summing over the free index rather than the bound one. Wilf calls it the snake oil method.

Lemma 3.69 (A shifted binomial series). For each fixed $k \geq 0$ ,

m \geq 0 \sum (k m) x^{m} = \frac{x ^{k}}{( 1 - x ) ^{k + 1}} .

Proof. Substituting $j = m - k$ (the terms with $m < k$ vanish) turns the sum into $\sum_{j \geq 0} (k j + k) x^{j + k} = x^{k} \sum_{j \geq 0} (k j + k) x^{j}$ , and by the negative-exponent corollary with $k + 1$ in place of $k$ the remaining sum is $\frac{1}{( 1 - x ) ^{k + 1}}$ .∎

Example 3.70 (The snake oil method). Prove that $k \geq 0 \sum (k n - k) = F_{n + 1}$ , the Fibonacci numbers with $F_{0} = 0$ , $F_{1} = 1$ .

Solution. Call the sum $s_{n}$ and form its generating function, then exchange the order of summation — legitimate because for each power of $x$ only finitely many terms contribute:

S (x) = n \geq 0 \sum s_{n} x^{n} = n \geq 0 \sum x^{n} k \geq 0 \sum (k n - k) = k \geq 0 \sum n \geq 0 \sum (k n - k) x^{n} .

In the inner sum substitute $n = m + k$ :

S (x) = k \geq 0 \sum x^{k} m \geq 0 \sum (k m) x^{m} = k \geq 0 \sum x^{k} \cdot \frac{x ^{k}}{( 1 - x ) ^{k + 1}}

by the shifted binomial lemma. Now sum the geometric series in $k$ , whose ratio $\frac{x ^{2}}{1 - x}$ has zero constant term so the sum is defined:

S (x) = \frac{1}{1 - x} k \geq 0 \sum (\frac{x ^{2}}{1 - x})^{k} = \frac{1}{1 - x} \cdot \frac{1}{1 - \frac{x ^{2}}{1 - x}} = \frac{1}{1 - x - x ^{2}} .

That is the generating function of $(F_{n + 1})_{n \geq 0}$ , as computed earlier. Comparing coefficients gives $s_{n} = F_{n + 1}$ .

Check. $n = 4$ : $(0 4) + (1 3) + (2 2) = 1 + 3 + 1 = 5 = F_{5}$ . The identity is the statement that the shallow diagonals of Pascal's triangle sum to Fibonacci numbers, and the proof above never had to see that picture.□

Summary (The whole method in one page).

A generating function is an element of $K [[x]]$ ; equality means equality of coefficients, and no substitution of numbers occurs.
$A$ is invertible iff $a_{0} \neq = 0$ ; $\frac{1}{1 - A}$ and $A (B)$ require order at least $1$ for the inner series.
Disjoint union is $+$ , product is $\times$ , sequence is $\frac{1}{1 - A}$ — for OGFs with sizes adding, for EGFs with labels distributed.
Sets and cycles of labelled components are $exp (A)$ and $ln \frac{1}{1 - A}$ ; the first is the exponential formula and is the workhorse of labelled enumeration.
A sequence satisfies a linear constant-coefficient recurrence iff its OGF is rational; partial fractions then gives $a_{n} = \sum p_{i} (n) r_{i}^{n}$ .
A convolution recurrence gives an algebraic equation (Catalan, Motzkin); a polynomial-coefficient recurrence gives a differential equation (involutions, Bell).
Coefficients come out by the generalised binomial theorem, by partial fractions, by convolution, or by Lagrange inversion for equations of the form $F = x ϕ (F)$ .
Always verify the first few coefficients by hand.

Exercises for §3.9 →

Common Mistakes

Reading a formal series as a convergent function. $\sum n! x^{n}$ is a legitimate formal power series and $\frac{1}{1 - x} = \sum x^{n}$ holds with no reference to $∣ x ∣ < 1$ . Convergence becomes relevant only when you want asymptotics.
Applying $\frac{1}{1 - A}$ when $A$ has a non-zero constant term. The construction is then undefined, not merely divergent (the Composition Theorem); combinatorially it means your class has infinitely many objects of some size.
Forgetting the $x^{0}$ term. The empty object contributes the constant $1$ to almost every generating function, and dropping it shifts every subsequent coefficient.
Confusing "any number of" with "at most one". Unlimited copies of an item of size $k$ give the factor $\frac{1}{1 - x ^{k}}$ ; a single optional copy gives $(1 + x^{k})$ . Euler's distinct-equals-odd theorem is exactly the statement that the difference matters.
Using a product when the decomposition is ambiguous. the Product Rule requires each object to arise from exactly one pair. Over-counting here is the single most common source of a wrong generating function.
Marking the wrong parameter. The exponent of $x$ must be the statistic you are counting by. If a problem tracks two statistics, you need two variables, and a bivariate generating function.
Reporting $[x^{n}] A (x)$ as the answer. For an EGF the count is $n! [x^{n}] A (x)$ .
Using an EGF for unlabelled objects. Partitions of an integer, tilings and coin problems have no labels to distribute; the $\frac{1}{n !}$ then normalises by a symmetry that is not there, and the constructions theorem does not apply.
Swapping "set of" and "sequence of". $SET$ is $exp (A)$ ; $SEQ$ is $\frac{1}{1 - A}$ . They differ by exactly the $k!$ orderings of the components.
Using $exp (A)$ when components may be empty. All three labelled constructions require $a_{0} = 0$ , for the same summability reason as in the ordinary case.
Forgetting that $e^{x}$ here is a formal series. $e^{x}$ , $ln \frac{1}{1 - x}$ and $(1 + x)^{α}$ are defined by their coefficients; their identities are proved formally, and no value is ever substituted for $x$ .
Mistaking an EGF for a probability generating function. A PGF is $\sum p_{n} x^{n}$ with $\sum p_{n} = 1$ and is evaluated at real $x$ ; the $\frac{1}{n !}$ of an EGF is a labelling correction, not a probability.
Mishandling the initial terms when shifting. $\sum_{n \geq 2} a_{n - 1} x^{n}$ is $x (A (x) - a_{0})$ , not $x A (x)$ . Almost every wrong generating function for a recurrence is wrong here.
Omitting the initial conditions. A recurrence of order $d$ describes a $d$ -parameter family of sequences; the numerator $P (x)$ is where the initial conditions live, and without them there is no single answer.
Ignoring root multiplicity. A root of multiplicity $m$ contributes $p (n) r^{n}$ with $de g p \leq m - 1$ , not just $α r^{n}$ ; the polynomial factor comes from $(j - 1 n + j - 1)$ in the expansion of $\frac{1}{( 1 - r x ) ^{j}}$ .
Sign errors in the characteristic polynomial. Bring everything to one side first: $a_{n} - c_{1} a_{n - 1} - \dots - c_{d} a_{n - d} = 0$ gives $χ (t) = t^{d} - c_{1} t^{d - 1} - \dots - c_{d}$ , the reverse of the denominator $Q (x)$ .
Taking the wrong root of a quadratic functional equation. Only one branch is a formal power series; decide by comparing constant terms, never by evaluating at a number.
Assuming every recurrence is linear with constant coefficients. Convolution recurrences and polynomial-coefficient recurrences are common and have their own machinery; a rational generating function is not the only good outcome.
Skipping the check. Expanding the first four coefficients of the final answer and comparing against a hand count catches essentially every algebra slip, and costs a minute.

About the practice questions. They check that you can carry out this chapter's computations correctly, and each one is graded on a single answer. They are not proof exercises: working through them confirms the mechanics, not that you could prove the results yourself. For that, re-read the statements above and try to reconstruct their proofs with the page closed.

Practice this chapter