Introduction to Mathematical Induction
Key Terms
- Mathematical induction
- A proof technique for statements P(n) that must hold for all integers n ≥ n0.
- Step 1 — Base case
- Verify that P(1) (or P(n0)) is true by direct calculation.
- Step 2 — Inductive hypothesis
- Assume P(k) is true for some arbitrary integer k ≥ 1.
- Step 3 — Inductive step
- Using the hypothesis, PROVE that P(k+1) is also true; show the logic, not just the algebra.
- Step 4 — Conclusion
- State: “By the principle of mathematical induction, P(n) is true for all n ≥ 1.”
- Domino analogy
- Base case = first domino falls; inductive step = each domino knocks over the next; together they guarantee all fall.
The Principle of Mathematical Induction
To prove a statement P(n) is true for all integers n ≥ 1:
Step 1 — Base case: Show P(1) is true.
Step 2 — Inductive hypothesis: Assume P(k) is true for some integer k ≥ 1.
Step 3 — Inductive step: Using the assumption from Step 2, prove that P(k+1) is also true.
Step 4 — Conclusion: By the principle of mathematical induction, P(n) is true for all n ≥ 1.
| The Domino Analogy | Mathematical Induction |
|---|---|
| The first domino falls (base case) | P(1) is true |
| If domino k falls, it knocks over domino k+1 | P(k) ⇒ P(k+1) |
| Therefore, every domino eventually falls | P(n) is true for all n ≥ 1 |
Worked Example — Prove 1 + 2 + 3 + … + n = n(n+1)/2
Step 1 — Base case (n = 1):
LHS = 1 RHS = 1(1+1)/2 = 2/2 = 1 LHS = RHS ✓
Step 2 — Inductive hypothesis:
Assume that for some integer k ≥ 1: 1 + 2 + 3 + … + k = k(k+1)/2
Step 3 — Inductive step: We must show P(k+1) is true, i.e. 1 + 2 + … + (k+1) = (k+1)(k+2)/2
Starting from the LHS for n = k+1:
1 + 2 + … + k + (k+1)
= k(k+1)/2 + (k+1) [by the inductive hypothesis]
= (k+1)[k/2 + 1]
= (k+1)(k+2)/2 [this is exactly RHS for n = k+1] ✓
Step 4 — Conclusion:
Since P(1) is true, and P(k) ⇒ P(k+1) for all k ≥ 1, by the principle of mathematical induction, 1 + 2 + 3 + … + n = n(n+1)/2 for all n ≥ 1.
Why Does Induction Work?
Mathematical induction uses two facts together to prove something holds for every positive integer. Think of an infinite line of dominoes. Two conditions guarantee every domino falls:
- The first domino is knocked over (the base case).
- Whenever any particular domino falls, it knocks the next one over (the inductive step).
Together, these facts guarantee the 1st falls, then the 2nd, then the 3rd — and so on forever. Induction works the same way with propositions about integers.
Induction vs. Checking Examples
You might think: "I've checked n = 1, 2, 3, 4, 5 and the formula works — so it must always work." This is not a proof. There are famous examples of patterns that hold for thousands of cases before eventually failing. The power of induction is that it gives a guaranteed chain of reasoning that covers every single positive integer, without exception.
The Critical Structure of the Inductive Step
The most important thing to understand is what the inductive step actually asks you to do:
- You assume P(k) is true (this is the inductive hypothesis — a working assumption, not something you have proved yet).
- Using that assumption, you derive that P(k+1) must also be true.
- The assumption and the derivation together form a valid logical implication: P(k) ⇒ P(k+1).
Do NOT substitute both "n = k" and "n = k+1" and call them equal. This is circular. You must start from P(k) and show P(k+1) follows via algebra.
In Step 3, always write:
LHS for n = k+1 = (sum to k) + (extra term)
= [RHS for n = k, by hypothesis] + (extra term)
= … (factor and simplify) …
= RHS for n = k+1 ✓
Common Mistakes to Avoid
| Mistake | Why It's Wrong | Fix |
|---|---|---|
| Skipping the base case | Without P(1), the chain has no starting link — nothing falls | Always verify P(1) explicitly with numbers |
| Circular reasoning | Assuming P(k+1) to prove P(k+1) | Start from P(k) only; derive P(k+1) by algebra |
| "Assume n = k and n = k+1" | n can't simultaneously equal two different things | Assume P(k) is true, then prove P(k+1) separately |
| Not connecting to the hypothesis | The algebra never uses the assumed P(k) | Explicitly cite the hypothesis at the substitution step |
Writing Up a Full Proof
A complete induction proof always contains all four labelled steps. In an exam, markers look for:
- A clear statement of what you are proving (P(n)).
- An explicit base case with LHS and RHS evaluated.
- The inductive hypothesis written out in full as an equation.
- The inductive step starting from LHS of P(k+1), using the hypothesis, ending at RHS of P(k+1).
- A conclusion sentence referencing the principle of mathematical induction.
Mastery Practice
-
Fluency
Q1 — The Four Steps
State the four steps of a proof by mathematical induction in your own words, explaining the purpose of each step.
-
Fluency
Q2 — Base Case Verification
Verify the base case (n = 1) for the claim: 1 + 3 + 5 + … + (2n − 1) = n².
-
Fluency
Q3 — Writing P(k) and P(k+1)
Write out what P(k) and P(k+1) look like for the claim: 1 + 2 + 3 + … + n = n(n+1)/2.
-
Fluency
Q4 — Prove the Triangular Number Formula
Prove by induction: 1 + 2 + 3 + … + n = n(n+1)/2 for all n ≥ 1.
-
Understanding
Q5 — Sum of Even Numbers
Prove by induction: 2 + 4 + 6 + … + 2n = n(n+1) for all n ≥ 1.
-
Understanding
Q6 — Sum of Odd Numbers
Prove by induction: 1 + 3 + 5 + … + (2n − 1) = n² for all n ≥ 1.
-
Understanding
Q7 — Sum of Squares
Prove by induction: 1² + 2² + 3² + … + n² = n(n+1)(2n+1)/6 for all n ≥ 1.
-
Understanding
Q8 — Spot the Error
A student writes: "I proved P(k), therefore P(k+1) is true." Explain clearly why this is not a valid inductive step.
-
Problem Solving
Q9 — Sum of Odd Numbers (Verify then Prove)
Consider the claim: the sum of the first n odd numbers equals n².
(a) Verify this for n = 1, 2, 3, 4 by directly computing both sides.
(b) Prove the claim by mathematical induction for all n ≥ 1.
-
Problem Solving
Q10 — n² + n is Always Even
(a) Verify for n = 1, 2, 3 that n² + n is even.
(b) Prove by induction that n² + n is even for all n ≥ 1.