9.1 The Idea: Sequences as Power Series

The (ordinary) generating function of a sequence a(0), a(1), a(2), ... is the formal power series

G(x) = a(0) + a(1)x + a(2)x^2 + ... = Σ a(n)·x^n

The powers of x act as labeled slots; x is a bookkeeping symbol, never evaluated, so convergence is irrelevant. We write [x^n] G(x) for "the coefficient of x^n in G". Generating functions convert counting problems and recurrences into algebra on series.

9.2 The Standard Series (Memorize This Table)

The fourth row is the powerhouse: it counts multisets — ways to choose n objects from k types with repetition allowed.

9.3 Operations on Generating Functions

If F(x) ↔ a(n) and G(x) ↔ b(n):

• Addition: F + G ↔ a(n) + b(n).
• Scaling / shifting: c·F ↔ c·a(n); x^m·F ↔ the sequence delayed by m places.
• Product (convolution): F·G ↔ Σ (k = 0 to n) a(k)·b(n−k) — exactly the rule for "split n between two independent choices", which is why products of GFs model combined selections.

9.4 Worked Example 1 — Counting Integer Solutions

(a) Unrestricted. How many non-negative integer solutions has x1 + x2 + x3 = 8?

1. Each variable contributes the factor (1 + x + x^2 + ...) = 1/(1 − x); three variables give G(x) = 1/(1 − x)^3.
2. By the table, [x^8] 1/(1 − x)^3 = C(8 + 3 − 1, 3 − 1) = C(10, 2) = 45.

(b) With bounds. Same equation but each xi must satisfy 2 ≤ xi ≤ 5. Now each factor is (x^2 + x^3 + x^4 + x^5) and G(x) = (x^2 + x^3 + x^4 + x^5)^3 = x^6·(1 + x + x^2 + x^3)^3. We need [x^8] G = [x^2] (1 + x + x^2 + x^3)^3. Choosing exponents summing to 2 from three brackets: (0,0,2) in 3 orders, (0,1,1) in 3 orders → 6 solutions. Equivalently: substitute yi = xi − 2 to get y1 + y2 + y3 = 2 with 0 ≤ yi ≤ 3, i.e., C(4, 2) = 6. ✔ Both methods agree.

9.5 Worked Example 2 — Solving a Recurrence with a GF

Problem: a(n) = 3a(n−1) for n ≥ 1, a(0) = 2. (Answer is obvious — which makes the machinery easy to watch.)

1. Let G(x) = Σ a(n)x^n. Multiply the recurrence by x^n and sum over n ≥ 1:

Σ (n≥1) a(n)x^n = 3x · Σ (n≥1) a(n−1)x^(n−1).

2. The left side is G(x) − a(0) = G(x) − 2; the right side is 3x·G(x).
3. So G(x) − 2 = 3x·G(x) → G(x) = 2/(1 − 3x).
4. By the table (row 1/(1 − ax)): a(n) = 2·3^n. ✔

For two-term recurrences the same procedure produces a rational function whose partial-fraction decomposition hands back exactly the A·r1^n + B·r2^n form of Lesson 8 — the two methods are one theory. Applying it to Fibonacci gives G(x) = x/(1 − x − x^2), whose partial fractions yield Binet's formula.

9.6 Common Mistakes & CS Applications

• Off-by-one index shifts: x^m·G delays a sequence; forgetting the a(0) term when summing a recurrence corrupts the algebra.
• Using C(n + k − 1, k − 1) when variables have upper bounds — bounds change the factors, as in 9.4(b).
• Treating x as a number and worrying about convergence — formal series need no convergence.
• Applications: the GF of the Catalan numbers C(x) satisfies C = 1 + x·C^2, counting binary trees and balanced parentheses; GF products compute the number of ways to make change (coin systems); probability generating functions give expected values of randomized algorithms; polynomial multiplication of GFs is what FFT accelerates.

🎯 Exam Focus

1. Define the ordinary generating function of a sequence. Write the GF of 1, 2, 3, 4, ... and of 0, 1, 0, 1, 0, 1, ....
2. Find the generating function for the number of ways to select n balls from unlimited red, blue, and green balls.
3. Using generating functions, count the solutions of x1 + x2 + x3 + x4 = 10 with each xi ≥ 1.
4. Find [x^5] in 1/(1 − 2x) and in (1 + x)^8.
5. Solve a(n) = 2a(n−1) + 1, a(0) = 0 using generating functions (answer: 2^n − 1).
6. How many ways can 12 identical chocolates be distributed among 3 children so that each gets between 2 and 6?