The Principle of Mathematical Induction
What you'll learn: How to prove statements about all natural numbers using a two-step domino effect.
The Core Idea
Mathematical induction is a powerful proof technique for statements indexed by natural numbers (like n = 1, 2, 3, ...). Instead of checking infinitely many cases one-by-one, induction works like toppling dominoes: prove the first domino falls, then prove that whenever one domino falls, the next one must fall too. This guarantees all dominoes fall.
The Two-Step Structure
Step 1: Base Case
Verify the statement is true for the starting value (usually n = 1 or n = 0). This is like pushing the first domino.
Step 2: Inductive Step
Assume the statement is true for some arbitrary natural number k (this assumption is called the inductive hypothesis). Then prove the statement must also be true for k + 1. This is like showing that if domino k falls, it knocks over domino k + 1.
Why It Works
Induction relies on the well-ordering principle of natural numbers: every natural number can be reached by starting at 1 and adding 1 repeatedly. If the base case holds and each step leads to the next, you've created an unbreakable chain proving the statement for all natural numbers.
Example Pattern
To prove "For all n ≥ 1, the sum 1 + 2 + ... + n = n(n+1)/2":
- Base case: When n = 1, left side = 1, right side = 1(2)/2 = 1. ✓
- Inductive step: Assume true for k. Show it's true for k + 1 using that assumption.
Key Takeaway: Mathematical induction proves infinitely many statements in two finite steps: establish the base case and prove the inductive chain reaction.