Prove infinite statements using the domino effect
Knock over the first domino, make sure each one topples the next, and every domino falls. That is induction: two steps that prove infinitely many statements.
Set the number of dominoes, then press Knock First Domino and watch the base case start a chain reaction.
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).
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."
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.
Step n up and down to grow the staircase, and turn on the doubling trick to see why 1 + 2 + ... + n = n(n+1)/2.
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 ✓
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.
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.
Choose a statement, then open and complete the base case, the inductive hypothesis, and the inductive step in turn.
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.
Spot a mistake or have an idea?