Explanation
Welcome to The Domino Hall
How can you prove something for every natural number without checking them all? Line them up like dominoes.
Push the first one, show that each one knocks over the next, and they all fall. That's mathematical induction.
Dominoes
Picture a line of dominoes that never ends. If the first one falls, and every falling domino knocks over the next, then every domino falls.
Induction proves statements the same way.
Dominoes: the first falls · each one knocks the next → all fall
Step 1
Three steps. First, check the statement for n equals one.
Second, assume it's true for some k: that's the induction hypothesis. Third, use that assumption to prove it for k plus one.
Step 1: check P(1) · Step 2: assume P(k) · Step 3: prove P(k + 1) using P(k)
Sums
For a sum, start from the formula for k and add the next term to both sides. Factor, and the formula for k plus one should appear.
Sums: 1 + 2 + … + k = k(k + 1)/2 → add (k + 1) → (k + 1)(k + 2)/2
Divisibility
For divisibility, rewrite the k plus one case so the k case shows up inside it. Five to the k plus one minus one is five times five to the k minus one, plus four.
Both parts are divisible by four.
Divisibility: 5ᵏ⁺¹ − 1 = 5(5ᵏ − 1) + 4
Inequalities may start later
Sometimes the first domino isn't at one. Two to the n beats n squared only from n equals five onwards.
Your base case then starts at five.
Inequalities may start later: 2ⁿ > n² is false for n = 2, 3, 4 and true from n = 5
Worked example
Show 4 divides 7ⁿ − 3ⁿ. P(1): 7 − 3 = 4.
Assume 4 divides 7ᵏ − 3ᵏ. Then 7ᵏ⁺¹ − 3ᵏ⁺¹ = 7(7ᵏ − 3ᵏ) + 4 × 3ᵏ, and both parts are multiples of 4.