The principle of mathematical induction proves statements P(n) for all natural numbers n >= n0. Step 1 (Base case): Verify P(n0) is true by direct substitution. Step 2 (Inductive step): Assume P(k) is true for an arbitrary k >= n0 (inductive hypothesis), then prove P(k+1) is true. If both steps succeed, P(n) holds for all n >= n0. The domino analogy: the base case pushes the first domino, and the inductive step ensures each domino knocks over the next. Common applications: sum formulas $\frac{1+2+...+n = n(n+1}{2}$), divisibility results ($n^{3-n}$ is divisible by 6), inequalities (2^n > n for n >= 1). Strong induction assumes P(n0) through P(k) are all true to prove P(k+1) — useful when the proof requires more than just the immediately preceding case.