Mathematical Induction

Number Theory · Axiom Academy

A powerful proof technique for establishing statements about all natural numbers Imagine an infinite line of dominoes. How can we be sure they will all fall? The first domino falls (Base Case) Each domino knocks down the next one (Inductive Step) If both conditions hold, then all dominoes will fall. This is the essence of mathematical induction! To prove a statement P(n) for all natural numbers n ≥ 1: Prove that P(1) is true (or P(n₀) for some starting value n₀) Assume P(k) is true for some arbitrary k ≥ 1 Then prove that P(k+1) must also be true This assumption that P(k) is true is called the inductive hypothesis 3. Formal Statement of Induction Using logical notation, the principle of mathematical induction states: P(1) = "P is true for n = 1" (base case) ∀k[P(k) → P(k+1)] = "For all k, if P(k) is true, then P(k+1) is true" ∧ = "and" (both conditions must hold) ∀n P(n) = "P is true for all natural numbers n" 4. Why Induction Works: Connection to WOP Mathematical induction is actually equivalent to the Well-Ordering Principle (WOP): Proof by contradiction: Suppose P(1) is true and P(k) → P(k+1) for all k, but there exists some n where P(n) is false. Let S = n ∈ ℕ : P(n) is false . By WOP, S has a smallest element m. Since P(1) is true, m > 1, so m - 1 exists Since m is the smallest counterexample, P(m-1) must be true But P(m-1) → P(m) by the inductive step, so P(m) is true Contradiction! Therefore S must be empty 5. Template for Induction Proofs

This is the written version of the interactive lesson above. See the full Number Theory course.