Strong Induction

Number Theory · Axiom Academy

A more powerful form of mathematical induction that assumes all previous cases hold 1. Understanding Strong Induction In weak (standard) induction , we prove P(n) for all n by: Inductive step: Assume P(k) is true, then prove P(k+1) is true In strong induction , the inductive step is different: Base case: Prove P(1) is true (sometimes more base cases) Inductive step: Assume P(1), P(2), ..., P(k) are all true, then prove P(k+1) is true Formal Statement of Strong Induction If P(1) is true, and for all k, if P(1) through P(k) are all true then P(k+1) is true, then P(n) is true for all positive integers n. While the two forms appear different, they are logically equivalent. Here's a detailed comparison: 3. When to Use Strong Induction Strong induction is particularly useful when the value at k+1 depends on multiple previous values, or when the recursive structure naturally looks back more than one step. Classic Indicators for Strong Induction: Fibonacci-type sequences: F(n) = F(n-1) + F(n-2) requires both previous terms Prime factorization: Breaking n into smaller factors requires knowing all smaller cases Division problems: When n divides into quotients of unpredictable size Game theory: Positions depend on multiple previous positions 4. Classic Example: Prime Factorization Theorem: Every integer n greater than 1 can be expressed as a product of prime numbers. Base case (n = 2): The number 2 is prime, so it is its own prime factorization.

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