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.”
- “If something is true for \(n=k\), then something is true for \(n=k+1\) too.”
The metaphor is to see the claim you’re trying to prove as a sequence of dominoes, stretching infinitely in one direction. To prove the claim, 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 \(1 + 2 + 3 + 4 = \frac{4(4+1)}{2},\) and so on and so on. First convince yourself that these base cases are true to your satisfaction (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, and clean up the right-hand-side until you have the equation \(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.