Olympiad problem-solving technique

Induction

Two finite steps climb an infinite ladder.

Prove the base case; prove that each case forces the next. The craft lives in the inductive step: find where the size- $(k+1)$ problem contains a size- $k$ copy of itself. Remove a disk, delete a vertex, strip the last term.

When the step will not go through, strengthen the statement. A stronger hypothesis gives the induction more to lean on, a beautiful paradox: proving more can be easier than proving less.

Where it appears on Lemma: Level 5, and beneath nearly every recursion you will ever write.

Train it on Lemma

Induction unlocks at Level 5 of Lemma's eight-level ladder, with lessons that teach it and drills that make it stick. 125 lessons, 1206 curated problems and unlimited generated practice at six difficulties. Free to start, no card, and every paid plan opens with 3 free days.

Find your level

More techniques

Ceva & MenelausConcurrency and collinearity are products of ratios.
InvariantsFind what the chaos cannot touch.
All 29 techniques →