Lemma › Techniques › Induction
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- problem contains a size- 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.
Guides on Induction
- EGMO 2021 Problem 1: solution, and why you only need to halveA full solution to EGMO 2021 Problem 1: build a chain from m to 2m out of the given moves, then halve 2021^2021 all the way down to 1.
- What separates a Level 5 problem from a Level 7, side by sideTwo IMO inequalities, both rated 5 out of 6, sit two rungs apart on the ladder. What actually separates a Level 5 problem from a Level 7, and how to cross.
- How to write up a proof so it gets full marksYour proof is right and the score is not. What a marker can and cannot credit, the four places marks leak out of a correct argument, and a read-back that finds them.
- Induction proofs where plugging in n+1 is not the stepFour inductive steps that plugging in n plus one will never close: a second predecessor, a stronger claim, a chosen deletion, and a base case that does not reach.
- Telescoping sums: how to spot them before you computeA telescoping sum announces itself before you do any algebra. Four signals that the middle will cancel, and the habit that kills the sign errors.
- How to get better at proofs when you can only computeComputation is not the wrong skill for proofs, it is an unfinished one. Five moves that turn arithmetic you can already do into an argument that holds.
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. 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
- Ceva & MenelausConcurrency and collinearity are products of ratios.
- InvariantsFind what the chaos cannot touch.
- All 29 techniques →