title: "Mathematical Induction"

Mathematical Induction

Definition. The principle of mathematical induction: if a statement $P(n)$ holds at $n = n_0$ (the base case), and for every $n \geq n_0$ the truth of $P(n)$ (the inductive hypothesis) implies the truth of $P(n + 1)$ (the inductive step), then $P(n)$ holds for every natural number $n \geq n_0$.

Proofs in this course must label all three parts. Introduced in Lecture 1; see Strong Induction for the variant that may use every earlier case.