Proof by Induction: Proving Statements About All Natural Numbers

Introduction

Mathematical induction is a proof technique for proving statements about all natural numbers or recursively defined structures. It’s one of the most powerful and widely used proof techniques in mathematics and computer science.

Understanding mathematical induction is essential for:

• Mathematics: Proving formulas and properties of natural numbers
• Computer Science: Proving properties of algorithms and data structures
• Discrete Mathematics: Proving combinatorial identities
• Formal Verification: Proving system properties
• Recursion: Understanding recursive algorithms

This comprehensive guide explores mathematical induction, its variations, and applications.

What is Mathematical Induction?

Definition

Mathematical induction is a proof technique that proves a statement P(n) is true for all natural numbers n by:

1. Proving P(1) is true (base case)
2. Proving that if P(k) is true, then P(k+1) is true (inductive step)

Why It Works

Mathematical induction works because:

• Base Case: We know P(1) is true
• Inductive Step: If P(k) is true, then P(k+1) is true
• Chain Reaction: P(1) → P(2) → P(3) → … → P(n) for all n

Structure

Goal: Prove ∀n ∈ ℕ P(n)

Base Case: Prove P(1) is true

Inductive Step:
  Assume: P(k) is true for some arbitrary k (inductive hypothesis)
  Prove: P(k+1) is true

Conclusion: By mathematical induction, P(n) is true for all n ∈ ℕ

Classic Examples

Example 1: Sum of First n Natural Numbers

Theorem: 1 + 2 + 3 + … + n = n(n+1)/2

Proof:

Base Case (n = 1):
  Left side: 1
  Right side: 1(1+1)/2 = 1(2)/2 = 1
  Both sides equal 1 ✓

Inductive Step:
  Assume: 1 + 2 + ... + k = k(k+1)/2 (inductive hypothesis)
  
  Prove: 1 + 2 + ... + k + (k+1) = (k+1)(k+2)/2
  
  Left side:
  1 + 2 + ... + k + (k+1)
  = k(k+1)/2 + (k+1)           [by inductive hypothesis]
  = k(k+1)/2 + 2(k+1)/2        [common denominator]
  = (k(k+1) + 2(k+1))/2        [combine fractions]
  = ((k+1)(k+2))/2             [factor out (k+1)]
  = (k+1)(k+2)/2
  
  This equals the right side ✓

Therefore, 1 + 2 + ... + n = n(n+1)/2 for all n ∈ ℕ

Example 2: Sum of Squares

Theorem: 1² + 2² + 3² + … + n² = n(n+1)(2n+1)/6

Proof:

Base Case (n = 1):
  Left side: 1² = 1
  Right side: 1(2)(3)/6 = 6/6 = 1
  Both sides equal 1 ✓

Inductive Step:
  Assume: 1² + 2² + ... + k² = k(k+1)(2k+1)/6
  
  Prove: 1² + 2² + ... + k² + (k+1)² = (k+1)(k+2)(2k+3)/6
  
  Left side:
  1² + 2² + ... + k² + (k+1)²
  = k(k+1)(2k+1)/6 + (k+1)²    [by inductive hypothesis]
  = (k+1)[k(2k+1)/6 + (k+1)]   [factor out (k+1)]
  = (k+1)[k(2k+1) + 6(k+1)]/6  [common denominator]
  = (k+1)[2k² + k + 6k + 6]/6  [expand]
  = (k+1)[2k² + 7k + 6]/6      [combine like terms]
  = (k+1)(k+2)(2k+3)/6         [factor 2k² + 7k + 6]
  
  This equals the right side ✓

Therefore, 1² + 2² + ... + n² = n(n+1)(2n+1)/6 for all n ∈ ℕ

Example 3: Powers of 2

Theorem: 2⁰ + 2¹ + 2² + … + 2ⁿ = 2ⁿ⁺¹ - 1

Proof:

Base Case (n = 0):
  Left side: 2⁰ = 1
  Right side: 2¹ - 1 = 2 - 1 = 1
  Both sides equal 1 ✓

Inductive Step:
  Assume: 2⁰ + 2¹ + ... + 2ᵏ = 2ᵏ⁺¹ - 1
  
  Prove: 2⁰ + 2¹ + ... + 2ᵏ + 2ᵏ⁺¹ = 2ᵏ⁺² - 1
  
  Left side:
  2⁰ + 2¹ + ... + 2ᵏ + 2ᵏ⁺¹
  = (2ᵏ⁺¹ - 1) + 2ᵏ⁺¹         [by inductive hypothesis]
  = 2·2ᵏ⁺¹ - 1                [combine like terms]
  = 2ᵏ⁺² - 1                  [exponent rule]
  
  This equals the right side ✓

Therefore, 2⁰ + 2¹ + ... + 2ⁿ = 2ⁿ⁺¹ - 1 for all n ∈ ℕ

Example 4: Divisibility

Theorem: 3 divides n³ - n for all n ∈ ℕ

Proof:

Base Case (n = 1):
  1³ - 1 = 1 - 1 = 0
  3 divides 0 ✓

Inductive Step:
  Assume: 3 divides k³ - k (so k³ - k = 3m for some integer m)
  
  Prove: 3 divides (k+1)³ - (k+1)
  
  (k+1)³ - (k+1)
  = k³ + 3k² + 3k + 1 - k - 1  [expand (k+1)³]
  = k³ + 3k² + 2k              [simplify]
  = (k³ - k) + 3k² + 3k        [rearrange]
  = (k³ - k) + 3(k² + k)       [factor out 3]
  = 3m + 3(k² + k)             [by inductive hypothesis]
  = 3(m + k² + k)              [factor out 3]
  
  Since m + k² + k is an integer, 3 divides (k+1)³ - (k+1) ✓

Therefore, 3 divides n³ - n for all n ∈ ℕ

Variations of Induction

Strong Induction

Strong induction (also called complete induction) assumes P(1), P(2), …, P(k) are all true, then proves P(k+1).

Structure:

Base Case: Prove P(1) is true

Inductive Step:
  Assume: P(1), P(2), ..., P(k) are all true
  Prove: P(k+1) is true

Conclusion: By strong induction, P(n) is true for all n ∈ ℕ

Example: Every integer greater than 1 can be expressed as a product of primes

Base Case (n = 2):
  2 is prime, so it's a product of primes ✓

Inductive Step:
  Assume: Every integer from 2 to k can be expressed as a product of primes
  
  Prove: k+1 can be expressed as a product of primes
  
  Case 1: k+1 is prime
    Then k+1 is a product of primes ✓
  
  Case 2: k+1 is composite
    Then k+1 = a·b where 1 < a, b < k+1
    By inductive hypothesis, both a and b are products of primes
    Therefore, k+1 = a·b is a product of primes ✓

Therefore, every integer > 1 is a product of primes

Induction Starting from n₀

Sometimes we want to prove P(n) for all n ≥ n₀ (not starting from 1).

Structure:

Base Case: Prove P(n₀) is true

Inductive Step:
  Assume: P(k) is true for some k ≥ n₀
  Prove: P(k+1) is true

Conclusion: By induction, P(n) is true for all n ≥ n₀

Example: 2ⁿ > n for all n ≥ 1

Base Case (n = 1):
  2¹ = 2 > 1 ✓

Inductive Step:
  Assume: 2ᵏ > k
  
  Prove: 2ᵏ⁺¹ > k+1
  
  2ᵏ⁺¹ = 2·2ᵏ > 2·k = 2k
  
  We need to show 2k > k+1, which is true when k ≥ 1.
  
  Therefore, 2ᵏ⁺¹ > k+1 ✓

Therefore, 2ⁿ > n for all n ≥ 1

Structural Induction

Structural induction proves properties of recursively defined structures (trees, lists, etc.).

Example: Every binary tree with n leaves has n-1 internal nodes

Base Case (n = 1):
  A tree with 1 leaf has 0 internal nodes
  1 - 1 = 0 ✓

Inductive Step:
  Assume: A tree with k leaves has k-1 internal nodes
  
  Prove: A tree with k+1 leaves has k internal nodes
  
  A tree with k+1 leaves can be formed by adding a leaf to a tree with k leaves.
  This adds one internal node.
  
  By inductive hypothesis, the original tree had k-1 internal nodes.
  Adding one internal node gives k internal nodes.
  
  Therefore, a tree with k+1 leaves has k internal nodes ✓

Therefore, every binary tree with n leaves has n-1 internal nodes

When to Use Induction

Good Candidates for Induction

1. Formulas About Natural Numbers

• Sum formulas: 1 + 2 + … + n = n(n+1)/2
• Power formulas: 2⁰ + 2¹ + … + 2ⁿ = 2ⁿ⁺¹ - 1

2. Divisibility Properties

• “3 divides n³ - n”
• “5 divides n⁵ - n”

3. Inequalities

• “2ⁿ > n for all n ≥ 1”
• “n! > 2ⁿ for all n ≥ 4”

4. Properties of Recursive Structures

• Properties of trees, lists, graphs
• Correctness of recursive algorithms

Poor Candidates for Induction

1. Statements About Specific Numbers

• “Is 17 prime?”
• “What is 2¹⁰?”

2. Statements That Don’t Generalize

• “This particular algorithm works”
• “This specific case is true”

Common Mistakes

Mistake 1: Forgetting the Base Case

Wrong:

Inductive Step: Assume P(k), prove P(k+1)
Conclusion: Therefore P(n) is true for all n

Correct: Must prove base case first!

Mistake 2: Not Using the Inductive Hypothesis

Wrong:

Assume P(k)
Prove P(k+1) without using P(k)

Correct: The inductive hypothesis must be used in the proof.

Mistake 3: Proving the Wrong Direction

Wrong:

Assume P(k+1), prove P(k)

Correct: Assume P(k), prove P(k+1)

Mistake 4: Incomplete Inductive Step

Wrong:

Assume P(k)
Show that P(k+1) is "similar" to P(k)

Correct: Must rigorously prove P(k+1) from P(k)

Practice Problems

Problem 1: Sum Formula

Theorem: 1 + 3 + 5 + … + (2n-1) = n²

Solution:

Base Case (n = 1):
  Left: 1
  Right: 1² = 1 ✓

Inductive Step:
  Assume: 1 + 3 + ... + (2k-1) = k²
  
  Prove: 1 + 3 + ... + (2k-1) + (2(k+1)-1) = (k+1)²
  
  Left side:
  1 + 3 + ... + (2k-1) + (2k+1)
  = k² + (2k+1)                [by inductive hypothesis]
  = k² + 2k + 1                [simplify]
  = (k+1)²                     [perfect square]
  
  This equals the right side ✓

Therefore, 1 + 3 + ... + (2n-1) = n² for all n ∈ ℕ

Problem 2: Divisibility

Theorem: 4 divides 5ⁿ - 1 for all n ≥ 1

Solution:

Base Case (n = 1):
  5¹ - 1 = 4, which is divisible by 4 ✓

Inductive Step:
  Assume: 4 divides 5ᵏ - 1 (so 5ᵏ - 1 = 4m)
  
  Prove: 4 divides 5ᵏ⁺¹ - 1
  
  5ᵏ⁺¹ - 1 = 5·5ᵏ - 1
           = 5(5ᵏ - 1) + 5 - 1    [rearrange]
           = 5(4m) + 4            [by inductive hypothesis]
           = 4(5m + 1)            [factor out 4]
  
  Since 5m + 1 is an integer, 4 divides 5ᵏ⁺¹ - 1 ✓

Therefore, 4 divides 5ⁿ - 1 for all n ≥ 1

Problem 3: Inequality

Theorem: n < 2ⁿ for all n ≥ 1

Solution:

Base Case (n = 1):
  1 < 2¹ = 2 ✓

Inductive Step:
  Assume: k < 2ᵏ
  
  Prove: k+1 < 2ᵏ⁺¹
  
  k+1 < 2ᵏ + 1                 [add 1 to both sides of assumption]
      < 2ᵏ + 2ᵏ                [since 1 < 2ᵏ for k ≥ 1]
      = 2·2ᵏ                   [combine like terms]
      = 2ᵏ⁺¹                   [exponent rule]
  
  Therefore, k+1 < 2ᵏ⁺¹ ✓

Therefore, n < 2ⁿ for all n ≥ 1

Related Resources and Tools

Online Learning Platforms

• Stanford Encyclopedia of Philosophy - Mathematical Induction - Academic treatment
• Khan Academy - Mathematical Induction - Video tutorials
• Coursera - Discrete Mathematics - University course
• MIT OpenCourseWare - Mathematics for Computer Science - Free materials

Interactive Tools

• Proof Checker - Fitch Proof Checker - Verify proofs
• Logic Simulator - LogicSim - Visual logic design
• Induction Visualizer - Wolfram MathWorld - Visualize induction
• Truth Table Generator - Stanford Tool - Create tables

Recommended Books

• “How to Prove It” by Daniel J. Velleman - Comprehensive proof guide
• “Concrete Mathematics” by Graham, Knuth, Patashnik - Induction and discrete math
• “Introduction to Logic” by Irving M. Copi and Carl Cohen - Classic textbook
• “forall x: An Introduction to Formal Logic” by P.D. Magnus - Free online textbook

Academic Journals

• Journal of Symbolic Logic - Leading journal on mathematical logic
• Studia Logica - International journal on logic and philosophy
• Logic and Logical Philosophy - Open access journal

Software Tools

• Prolog - Logic programming language
• Coq - Interactive theorem prover
• Isabelle - Generic proof assistant
• Z3 - SMT solver

Glossary of Key Terms

• Base Case: Initial case proven directly
• Inductive Hypothesis: Assumption that P(k) is true
• Inductive Step: Proof that P(k) implies P(k+1)
• Mathematical Induction: Proof technique for natural numbers
• Strong Induction: Induction assuming all previous cases
• Structural Induction: Induction on recursive structures

Conclusion

Mathematical induction is a powerful and fundamental proof technique. By mastering induction, you develop the ability to:

• Prove formulas about natural numbers
• Verify properties of recursive algorithms
• Understand recursive structures
• Construct rigorous mathematical proofs
• Apply logic to discrete mathematics

The next article in this series will explore Proof by Cases, a technique for proving statements by considering all possible cases.

---

What’s your favorite induction proof? Have you used induction to prove properties of algorithms? Share your examples in the comments below!