What is the principle of mathematical induction?
Some statements talk about every natural number n = 1, 2, 3, … . We cannot check them one by one for ever. Induction is a way to prove all of them at once.
Let P(n) be a statement about n. If
- Base case: P(1) is true, and
- Inductive step: whenever P(k) is true, P(k + 1) is also true,
then P(n) is true for every natural number n.
The assumption "P(k) is true" is called the inductive hypothesis. We do not prove it; we use it to reach P(k + 1).
The base case can start at another number. For example, to prove something for n ≥ 4, check P(4) first.
How to write an induction proof
- Write the statement P(n) clearly.
- Base case: put n = 1 (or the first value). Work out both sides and show they are equal.
- Assume P(k) is true for some natural number k. Write it out.
- Target: write P(k + 1), what you must reach.
- Start from one side of P(k + 1), use P(k) somewhere, and work until you get the other side.
- Conclude: "Since P(1) is true and P(k) ⇒ P(k + 1), by induction P(n) is true for all n ≥ 1."
Worked proof: sum of the first n numbers
P(n): 1 + 2 + … + n = n(n + 1)/2.
Base: n = 1: left = 1, right = 1 × 2/2 = 1 ✓.
Assume 1 + … + k = k(k + 1)/2. Then 1 + … + k + (k + 1) = k(k + 1)/2 + (k + 1) = (k + 1)(k + 2)/2, which is P(k + 1) ✓.
Types of induction proofs
1. Sums (series)
Add the next term (the (k + 1)th term) to both sides of P(k), then simplify.
2. Divisibility
Example: 3 divides 4ⁿ − 1. Base: 4 − 1 = 3 ✓. Assume 4ᵏ − 1 = 3m. Then 4ᵏ⁺¹ − 1 = 4 × 4ᵏ − 1 = 4(3m + 1) − 1 = 12m + 3 = 3(4m + 1) ✓.
3. Inequalities
Example: 2ⁿ > n. Base: 2 > 1 ✓. Assume 2ᵏ > k. Then 2ᵏ⁺¹ = 2 × 2ᵏ > 2k ≥ k + 1 (since k ≥ 1) ✓.
4. Sequences defined by a rule
If u₁ = 1 and uₙ₊₁ = 2uₙ + 1, prove uₙ = 2ⁿ − 1. Base: 2 − 1 = 1 ✓. Assume uₖ = 2ᵏ − 1. Then uₖ₊₁ = 2(2ᵏ − 1) + 1 = 2ᵏ⁺¹ − 1 ✓. Induction is also used to show a sequence is increasing or bounded.
Strong induction (extra)
Sometimes you assume P(1), …, P(k) are all true to prove P(k + 1). This is useful for rules that use two earlier terms, like the Fibonacci numbers.
Why both steps are needed
No base case: the statement "n + 1 = n" has a working inductive step (if k + 1 = k then k + 2 = k + 1), but it is false for every n. Nothing starts the chain.
No inductive step: n² − n + 41 is prime for n = 1 to 40, but at n = 41 it equals 41², which is not prime. Checking many cases is not a proof.
Key formulas and definitions
- Base case: P(1) true
- Inductive step: P(k) true ⇒ P(k + 1) true
- 1 + 2 + … + n = n(n + 1)/2
- 1² + 2² + … + n² = n(n + 1)(2n + 1)/6
- 1³ + 2³ + … + n³ = [n(n + 1)/2]²
- 1 + 3 + 5 + … + (2n − 1) = n²
Worked examples
1. Prove 1 + 3 + 5 + … + (2n − 1) = n².
Base: n = 1: 1 = 1² ✓. Assume 1 + 3 + … + (2k − 1) = k². Add the next odd number 2k + 1: k² + 2k + 1 = (k + 1)² ✓. So true for all n.
2. Prove 1² + 2² + … + n² = n(n + 1)(2n + 1)/6.
Base: 1 = 1·2·3/6 ✓. Assume true for k. Add (k + 1)²: k(k + 1)(2k + 1)/6 + (k + 1)² = (k + 1)[k(2k + 1) + 6(k + 1)]/6 = (k + 1)(2k² + 7k + 6)/6 = (k + 1)(k + 2)(2k + 3)/6 ✓.
3. Prove 5ⁿ − 1 is divisible by 4.
Base: 5 − 1 = 4 ✓. Assume 5ᵏ − 1 = 4m. Then 5ᵏ⁺¹ − 1 = 5(4m + 1) − 1 = 20m + 4 = 4(5m + 1) ✓.
4. Prove n³ − n is divisible by 6 for n ≥ 1.
Base: 0 is divisible by 6 ✓. Assume k³ − k = 6m. (k + 1)³ − (k + 1) = k³ + 3k² + 2k = (k³ − k) + 3k(k + 1) = 6m + 3k(k + 1). k(k + 1) is even, so 3k(k + 1) is a multiple of 6 ✓.
5. Prove 3ⁿ ≥ 2n + 1 for n ≥ 1.
Base: 3 ≥ 3 ✓. Assume 3ᵏ ≥ 2k + 1. Then 3ᵏ⁺¹ ≥ 3(2k + 1) = 6k + 3 ≥ 2k + 3 = 2(k + 1) + 1 ✓.
6. u₁ = 3 and uₙ₊₁ = uₙ + 4. Prove uₙ = 4n − 1.
Base: 4 − 1 = 3 ✓. Assume uₖ = 4k − 1. Then uₖ₊₁ = 4k − 1 + 4 = 4(k + 1) − 1 ✓.
Common mistakes
- Skipping the base case, or checking it only in your head. Always write both sides for n = 1.
- Assuming P(k + 1) is true. You may only assume P(k); P(k + 1) is what you must prove.
- Adding the wrong next term. In 1 + 3 + … + (2k − 1), the next term is 2(k + 1) − 1 = 2k + 1, not 2k − 1 + 1.
- Thinking that checking n = 1, 2, 3, 4 is enough. Many patterns break later; only the inductive step covers all n.