Generating Functions

Turn a sequence into a single function.

Encode a sequence $a_0, a_1, a_2, \dots$ as the coefficients of a power series $\sum a_n x^n$. Recurrences become algebraic equations, convolutions become products, and the answer falls out of a coefficient extraction.

The workhorse identities: $\frac{1}{1-x} = \sum x^n$ and $\frac{1}{(1-x)^k} = \sum \binom{n+k-1}{k-1} x^n$ — the second is stars and bars in disguise.

Best deployed when a counting problem has an awkward constraint that is easy to write as a factor of a product.

More techniques

• The Extremal PrincipleConsider the largest, the smallest, the closest.
• Smoothing & NormalisationNudge the variables toward equality and watch the bound improve.
• All 26 techniques →