If you’re looking to prove a statement of the form, “For all positive integers \(n\), something is true,” it’s sufficient to prove these two individual statements, which are often each easier to prove:
- “For \(n=1\) something is true.” (base case)
- “If something is true for \(n=k\), then something is true for \(n=k+1\) too.” (inductive step)
Metaphor: imagine the claim you’re trying to prove as a sequence of dominoes, stretching infinitely in one direction. To prove the claim you can simply prove that (1) the first domino must fall, and that (2) if any single domino falls, then the next domino in line will fall too.
Examples
Prove that for all positive integers \(n\),
we have \(\displaystyle 1 + 2 + \dotsb + n = \frac{n(n+1)}{2}\,.\)
This is really the claim that \(1 = \frac{1(1+1)}{2}\) and \(1 + 2 = \frac{2(2+1)}{2}\) and \(1 + 2 + 3 = \frac{3(3+1)}{2},\) and so on. First convince yourself that these base cases are true (the first domino must fall). Then assume that \(1 + 2 + \dotsb + k = \frac{k(k+1)}{2}\) for a particular positive integer \(k\) (if any single domino falls …), add \(k\!+\!1\) to both sides of that equation to prove that \(1 + 2 + \dotsb + k + (k\!+\!1) = \frac{(k\!+\!1)\left((k\!+\!1)+1\right)}{2}\) (… the next domino in line must fall too).
Suppose \(n\) lines are drawn in the plane, dividing it into regions.
Prove that these regions can be colored orange and blue
in such a way that neighboring regions,
ones sharing a line as a boundary, are different colors.