Mathematical Induction

What is Mathematical Induction?

Method of proof: Prove statement true for all natural numbers

Like dominos: If first falls and each knocks next, all fall

Two steps:

1. Base case: Prove true for n = 1 (or starting value)
2. Inductive step: Assume true for n = k, prove true for n = k+1

If both steps work, true for all n!

Structure of Induction Proof

1. State what to prove

2. Base case: Verify for n = 1 (or smallest n)

3. Inductive hypothesis: Assume true for n = k

4. Inductive step: Prove true for n = k+1 using hypothesis

5. Conclusion: By induction, true for all n

Example 1: Sum Formula

Prove: 1 + 2 + 3 + ... + n = n(n+1)/2

Base case (n = 1):

Left side: 1
Right side: 1(2)/2 = 1
Equal ✓

Inductive hypothesis: Assume true for n = k

1 + 2 + ... + k = k(k+1)/2

Inductive step: Prove for n = k+1

1 + 2 + ... + k + (k+1)
= [1 + 2 + ... + k] + (k+1)
= k(k+1)/2 + (k+1)        (by hypothesis)
= (k+1)[k/2 + 1]
= (k+1)(k+2)/2
= (k+1)[(k+1)+1]/2 ✓

Conclusion: True for all n ≥ 1 by induction

Example 2: Sum of Odd Numbers

Prove: 1 + 3 + 5 + ... + (2n-1) = n²

Base case (n = 1):

Left: 1
Right: 1² = 1 ✓

Hypothesis: Assume 1 + 3 + ... + (2k-1) = k²

Step: Prove for n = k+1

1 + 3 + ... + (2k-1) + (2(k+1)-1)
= k² + (2k+2-1)         (by hypothesis)
= k² + 2k + 1
= (k+1)² ✓

Conclusion: True for all n ≥ 1

Divisibility Proofs

Prove: Expression divisible by number for all n

Example: Prove 4ⁿ - 1 divisible by 3

Base case (n = 1):

4¹ - 1 = 3
Divisible by 3 ✓

Hypothesis: Assume 4ᵏ - 1 = 3m for some integer m

Step: Prove 4^(k+1) - 1 divisible by 3

4^(k+1) - 1 = 4·4ᵏ - 1
            = 4·4ᵏ - 4 + 3
            = 4(4ᵏ - 1) + 3
            = 4(3m) + 3      (by hypothesis)
            = 3(4m + 1)

Divisible by 3 ✓

Conclusion: True for all n ≥ 1

Inequality Proofs

Prove inequality holds for all n beyond threshold

Example: Prove 2ⁿ > n for n ≥ 1

Base case (n = 1):

2¹ = 2 > 1 ✓

Hypothesis: Assume 2ᵏ > k

Step: Prove 2^(k+1) > k+1

2^(k+1) = 2·2ᵏ
        > 2k        (by hypothesis)
        > k + 1     (since k ≥ 1, so 2k > k+1)

True ✓

Conclusion: 2ⁿ > n for all n ≥ 1

Geometric Formulas

Prove formulas for geometric sequences

Example: Geometric Sum

Prove: 1 + r + r² + ... + rⁿ = (rⁿ⁺¹ - 1)/(r - 1) for r ≠ 1

Base case (n = 0):

Left: 1
Right: (r - 1)/(r - 1) = 1 ✓

Hypothesis: Assume 1 + r + ... + rᵏ = (r^(k+1) - 1)/(r - 1)

Step:

1 + r + ... + rᵏ + r^(k+1)
= (r^(k+1) - 1)/(r - 1) + r^(k+1)    (by hypothesis)
= [r^(k+1) - 1 + r^(k+1)(r - 1)]/(r - 1)
= [r^(k+1) - 1 + r^(k+2) - r^(k+1)]/(r - 1)
= (r^(k+2) - 1)/(r - 1) ✓

Conclusion: True for all n ≥ 0

Strong Induction

Variant: Assume true for ALL values up to k, not just k

Use when: Need multiple previous cases

Steps same, but hypothesis stronger

Example: Fibonacci Bound

Prove: Fₙ < 2ⁿ for all n ≥ 1

Base cases:

F₁ = 1 < 2¹ = 2 ✓
F₂ = 1 < 2² = 4 ✓

Strong hypothesis: Assume Fᵢ < 2ⁱ for all i ≤ k

Step:

F_(k+1) = Fₖ + F_(k-1)
        < 2ᵏ + 2^(k-1)     (by hypothesis)
        < 2ᵏ + 2ᵏ
        = 2·2ᵏ
        = 2^(k+1) ✓

Conclusion: True for all n ≥ 1

Common Mistakes

❌ Circular reasoning: Using what you're proving in the proof

❌ Skipping base case: Base case is essential!

❌ Not using hypothesis: Must explicitly use hypothesis in step

❌ Proving backwards: Prove P(k) → P(k+1), not P(k+1) → P(k)

When to Use Induction

Ideal for:

• Formulas involving n
• Divisibility for all n
• Inequalities for all n ≥ threshold
• Recursive definitions

Not needed for:

• Single specific case
• Finite number of cases

Applications: Computer Science

Algorithm correctness: Prove loop invariants

Data structures: Prove properties of trees

Recurrence relations: Solve complexity formulas

Example: Binary Tree Nodes

Prove: Binary tree of height h has at most 2^(h+1) - 1 nodes

Base case (h = 0): 1 node, 2¹ - 1 = 1 ✓

Hypothesis: Tree of height k has ≤ 2^(k+1) - 1 nodes

Step: Tree of height k+1 has root plus two subtrees of height ≤ k

Nodes ≤ 1 + 2(2^(k+1) - 1)
      = 1 + 2^(k+2) - 2
      = 2^(k+2) - 1 ✓

Well-Ordering Principle

Related concept: Every non-empty set of positive integers has smallest element

Equivalent to induction

Sometimes easier approach for certain proofs

Practice