Mathematical Induction

Overview

The Power of Induction

Mathematical induction is a proof technique for statements of the form "For all integers n ≥ n₀, P(n) is true." Think of it like knocking down an infinite row of dominoes: if you knock down the first one (base case) and every domino knocks down the next (inductive step), then all dominoes fall.

Definition

Principle of Mathematical Induction

To prove that P(n) holds for all n ≥ n₀:

1. Base Case: Show P(n₀) is true. 2. Inductive Step: For an arbitrary k ≥ n₀, assume P(k) is true (the inductive hypothesis), and prove that P(k + 1) is true.

Conclusion: P(n) is true for all integers n ≥ n₀.

Example

Sum of First n Positive Integers

Theorem: For all n ≥ 1, 1 + 2 + 3 + ... + n = n(n + 1)/2.

Proof by Induction: Base Case (n = 1): LHS = 1. RHS = 1(2)/2 = 1. ✓

Inductive Step: Assume 1 + 2 + ... + k = k(k + 1)/2 for some k ≥ 1. Show: 1 + 2 + ... + k + (k + 1) = (k + 1)(k + 2)/2.

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

By induction, the formula holds for all n ≥ 1. QED.

Example

Sum of a Geometric Series

Theorem: For all n ≥ 0 and r ≠ 1, ∑ᵢ₌₀ⁿ rⁱ = (rⁿ⁺¹ - 1)/(r - 1).

Base Case (n = 0): LHS = r⁰ = 1. RHS = (r¹ - 1)/(r - 1) = 1. ✓

Inductive Step: Assume ∑ᵢ₌₀ᵏ rⁱ = (rᵏ⁺¹ - 1)/(r - 1). ∑ᵢ₌₀ᵏ⁺¹ rⁱ = (rᵏ⁺¹ - 1)/(r - 1) + rᵏ⁺¹ = (rᵏ⁺¹ - 1 + rᵏ⁺¹(r - 1))/(r - 1) = (rᵏ⁺¹ - 1 + rᵏ⁺² - rᵏ⁺¹)/(r - 1) = (rᵏ⁺² - 1)/(r - 1). ✓

By induction, the formula holds for all n ≥ 0. QED.

Definition

Strong Induction

In strong induction, the inductive hypothesis assumes P(n₀), P(n₀ + 1), ..., P(k) are ALL true (not just P(k)), and proves P(k + 1). Strong induction is equivalent to standard induction but can be easier to apply when P(k + 1) depends on multiple previous cases.

Example

Strong Induction: Fundamental Theorem of Arithmetic

Theorem: Every integer n ≥ 2 can be written as a product of primes.

Proof (Strong Induction): Base Case (n = 2): 2 is prime, so it is trivially a product of primes. ✓

Inductive Step: Assume every integer from 2 to k can be written as a product of primes. Consider k + 1.

Case 1: k + 1 is prime. Then it is a product of primes (just itself). ✓ Case 2: k + 1 is composite. Then k + 1 = a × b where 2 ≤ a, b ≤ k. By the inductive hypothesis, both a and b can be written as products of primes, so k + 1 = a × b is also a product of primes. ✓

By strong induction, every integer n ≥ 2 is a product of primes. QED.

Note

Common Induction Mistakes

1. Forgetting the base case - without it, the proof is invalid. 2. Not clearly stating the inductive hypothesis. 3. Trying to prove P(k) instead of P(k + 1) in the inductive step. 4. Using what you want to prove as an assumption (circular reasoning). 5. Choosing the wrong base case - make sure it matches the claim.