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

• Convexity & JensenBalance minimises what curves upward.
• Smoothing & NormalisationNudge the variables toward equality and watch the bound improve.
• All 29 techniques →