Lemma › Techniques › Generating Functions
Olympiad problem-solving technique
Generating Functions
Turn a sequence into a single function.
Encode a sequence as the coefficients of a power series . Recurrences become algebraic equations, convolutions become products, and the answer falls out of a coefficient extraction.
The workhorse identities: and . 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.
Guides on Generating Functions
- Generating functions: turning a counting problem into a productGenerating functions explained as a method: one factor per constraint, multiply, read the coefficient. The dictionary, and how to extract by hand.
Train it on Lemma
Generating Functions unlocks at Level 7 of Lemma's eight-level ladder, with lessons that teach it and drills that make it stick. 128 lessons, 1237 curated problems and unlimited generated practice at six difficulties. Free to start, no card, and the paid plan opens with 3 free days.
Find your levelMore techniques
- Convexity & JensenBalance minimises what curves upward.
- Smoothing & NormalisationNudge the variables toward equality and watch the bound improve.
- All 29 techniques →