Generating Functions

A generating function encodes a sequence $a_0, a_1, a_2, \ldots$ as: $$A(x) = \sum_{n=0}^{\infty} a_n x^n$$ Key operations: - Addition: $A(x) + B(x)$ adds sequences term-by-term - Multiplication: $A(x) \cdot B(x)$ gives the convolution $c_n = \sum_{k=0}^n a_k b_{n-k}$ - Differentiation: $A'(x) = \sum n a_n x^{n-1}$ shifts and weights - Substitution: $A(x^2)$ picks out even-indexed terms Common generating functions: - $\frac{1}{1-x} = 1 + x + x^2 + \cdots$ (geometric series) - $\frac{1}{(1-x)^2} = 1 + 2x + 3x^2 + \cdots$ - $e^x = 1 + x + \frac{x^2}{2!} + \cdots$ (exponential g.f.) - $\frac{1-\sqrt{1-4x}}{2x}$ generates Catalan numbers When to use: Solving linear recurrences with constant coefficients. Counting problems where you need to track a parameter. Proving combinatorial identities. This is a fundamental technique for combinatorics and probability. Many "narrow" identities (Vandermonde, Catalan formula) can be derived via generating functions.