Knock the first, and each knocks the next: Induction is like a line of dominoes: if you can knock over the first one, and show each domino knocks over the next, then they ALL fall.
So: prove it for n = 1, then show 'true for k' forces 'true for k + 1'.
1. Base case
- Show the statement is true for n = 1 (knock the first domino).
2. Assumption
- Assume the statement is true for some n = k.
3. Inductive step
- Using that assumption, prove it must be true for n = k + 1.
4. Conclusion
- True for n = 1, and each case forces the next, so true for all n ∈ ℤ⁺.
IB-style question — sum of the first n integers
Prove by induction that 1 + 2 + 3 + … + n = n(n + 1)/2 for all n ∈ ℤ⁺.
Step by step
- Base case n = 1: check both sides.
- Assume true for n = k.
- Step: add the next term (k + 1) to both sides.
- Factor out (k + 1).
- That is the formula with n = k + 1, so it's true for k + 1. Conclude: by induction, true for all n ∈ ℤ⁺.
Final answer
Proven by induction for all positive integers n.
Free preview
This is the free notes preview
You're reading the free notes. Aimnova Pro unlocks the full study experience — and you can try it with your first topic free to keep:
- FlashcardsLock in vocabulary and key terms with spaced repetition.
- Practice questionsAnswer exam-style questions and get instant AI marking.
- Mock exams & past-paper vaultSit full mocks and see exactly how examiners award marks.
- Personalised study planA daily plan built around your exam date and weak areas.
Start Studying Free Full access to Aimnova Pro · cancel anytime
Same four steps, divisibility flavour: Induction also proves divisibility. The trick in the step: write the (k + 1) expression so the assumption appears, then show the whole thing is still a multiple.
IB-style question — divisibility
Prove by induction that 6ⁿ − 1 is divisible by 5 for all n ∈ ℤ⁺.
Step by step
- Base case n = 1: 6¹ − 1 = 5, which is divisible by 5.
- Assume true for n = k: 6ᵏ − 1 = 5m for some integer m.
- Step: write 6k+1 − 1 to bring in 6ᵏ.
- Use the assumption 6ᵏ − 1 = 5m.
- A multiple of 5, so true for k + 1. Conclude: by induction, true for all n ∈ ℤ⁺.
Final answer
Proven by induction: 6ⁿ − 1 is always divisible by 5.