title: "Strong Induction"

Strong Induction

Definition. Strong induction proves that $P(n)$ holds for every $n \geq n_0$ from one implication: for every $n \geq n_0$, if $P(k)$ holds for all $n_0 \leq k < n$, then $P(n)$ holds. Unlike ordinary Mathematical Induction, the hypothesis grants every earlier case, not just the previous one.

Introduced in Lecture 1, Example 9; it returns in Unit 1 as structural induction on automata and grammars.