Strong vs Weak Induction

Intro to Proofs · Axiom Academy

LESSON Strong vs Weak Induction Two proof techniques with identical logical power — but one reaches back a single step, the other reaches back to every step. Learn when each one is the natural choice. Weak induction proves a statement P(n) for all natural numbers in two moves: nail down the first case, then show each case forces the very next one. Base case: prove P(n_0) (usually n_0 = 0 or 1 ). Inductive hypothesis: assume P(k) for some . Inductive step: prove P(k+1) follows from P(k) . Think of it like dominoes: prove the first one falls (base case), then show that whenever one falls the next must fall too (inductive step). Each fall depends only on the one right before it. Strong induction proves the same kind of statement, but grants a more generous hypothesis: when proving P(k+1) you may use every case below it, not just the last one. Base case(s): prove as needed. Inductive hypothesis: assume P(j) for all j with . Inductive step: prove P(k+1) using any or all previous cases. Instead of just assuming the previous domino fell, you assume all previous dominoes have fallen. The whole established run below is fair game when you build the next case — which gives you far more flexibility. 3. They're Logically Equivalent Here's the surprising truth: strong and weak induction have exactly the same logical power. Anything you can prove with one, you can prove with the other.

This is the written version of the interactive lesson above. See the full Intro to Proofs course.