To prove a statement of the form “For all positive integers \(n\), something is true.” it’s sufficient to prove these individual statements:
- “For \(n=1\) something is true.” ← This is the base case, \(P(1)\)
- “If something is true for \(n=k\), then something is true for \(n=k+1\) too.” ← This is the inductive step, \(P(k) \!\!\implies\!\! P(k+1)\)
Metaphor: imagine the statement you’re trying to prove as a line of standing dominoes, stretching infinitely in one direction. To prove the statement, you can simply prove (1) the first domino must fall, and (2) if any single domino falls, the next domino in line must fall too.
Examples of Statement that Suggest an Inductive Proof
Prove that for all positive integers \(n\),
we have \(\displaystyle 1 + 2 + \dotsb + n = \tfrac{n(n+1)}{2}\,.\)
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.
Non-Standard Induction & Cauchy Induction
The inductive scheme of statements “\(P(1),\) and \(P(k) \!\!\implies\!\! P(k+1)\)” is sufficient because it covers all positive integers. But this is only the standard scheme; any other inductive scheme that covers all positive integers works too, and is referred to as a non-standard induction. A notable example of non-standard induction, Cauchy Induction, employs the scheme “\(P(1),\) and \(P(k) \!\!\implies\!\! P(2k),\) and \(P(k) \!\!\implies\!\! P(k-1)\).”