Prove infinite statements using the domino effect
Mathematical induction is a powerful technique for proving statements about all natural numbers. Think of a line of dominoes: knock down the first one (base case) and prove each domino knocks down the next (inductive step), then all dominoes fall.
This lets us prove infinitely many statements with just two steps. Induction is the right tool for sum formulas, inequalities, divisibility properties, and any claim about "all n ≥ some starting value."
Watch the domino analogy play out. The base case knocks down domino 1, and the inductive step creates the chain reaction that reaches every number.
Mathematical induction works like falling dominoes: prove the first case falls (base case), then prove each domino knocks over the next (inductive step).
Base case: The first domino falls (we prove P(1) is true).
Inductive step: Each domino knocks over the next (we prove P(k) → P(k+1)).
Conclusion: All dominoes fall (P(n) is true for all n ≥ 1).
Key insight: Without the base case, the chain has no starting point. Without the inductive step, the chain breaks. Both pieces are essential -- you can "prove" false statements if you skip either one.
See a geometric proof of the classic formula 1 + 2 + ... + n = n(n+1)/2. The visual makes the inductive step intuitive -- adding the next row extends the pattern.
Visualize why the sum of the first n positive integers equals n(n+1)/2. This classic formula can be proven by induction!
Base case (n=1): 1 = 1(2)/2 = 1 ✓
Inductive step: If 1+2+...+k = k(k+1)/2, then
1+2+...+k+(k+1) = k(k+1)/2 + (k+1) = (k+1)(k+2)/2 ✓
Key insight: In the inductive step, the key move is using the inductive hypothesis P(k) to simplify the expression for P(k+1). If your proof of P(k+1) never references P(k), something is wrong.
Build a complete induction proof step by step. Choose a statement, establish the base case, state the inductive hypothesis, and complete the inductive step.
Walk through complete induction proofs step by step. Understand each part before moving on.
For all n ≥ 1: 1 + 2 + 3 + ... + n = n(n+1)/2
When n=1, both sides equal 1.
Key insight: The inductive hypothesis (assuming P(k)) is your main tool. The art of induction is finding a way to express P(k+1) in terms of P(k) plus something manageable.