Practice Flashcards
Flip to reveal answersWhat are the four steps of proof by induction?
Track your progress — Sign up free to save your progress and get smart review reminders based on spaced repetition.
All 8 Flashcards — Proof by induction
Sign up free to track progress and get spaced-repetition review schedules.
Question
What are the four steps of proof by induction?
Answer
Base case (n = 1), assume true for n = k, prove true for n = k + 1, conclude true for all n.
Question
What's the domino analogy for induction?
Answer
Knock the first domino (base case) and show each knocks the next (k ⇒ k + 1), so they all fall (all n).
Question
What must the inductive step USE?
Answer
The assumption (the result for n = k) — that's the link that proves n = k + 1.
Question
How do you finish an induction proof?
Answer
State the conclusion: true for n = 1 and 'true for k ⇒ true for k + 1', so true for all n ∈ ℤ⁺.
Question
Base case for 1 + 2 + … + n = n(n+1)/2?
Answer
n = 1: LHS = 1, RHS = 1(2)/2 = 1 ✓.
Question
In a divisibility induction, the key move in the step?
Answer
Rewrite the (k+1) expression so the assumption (e.g. 6ᵏ − 1 = 5m) appears, then factor out the divisor.
Question
Why is the base case essential?
Answer
Without a true starting case, the chain k ⇒ k + 1 never gets going — nothing is ever shown true.
Question
What does 'assume true for n = k' mean?
Answer
Take the statement as given for one (unspecified) value k, so you can use it to prove the next case.
Read the notes
Full study notes for Proof by induction
Topic 1.15 hub
Proof by induction (HL only)
More from Topic 1.15
All flashcards in this topic
Math AA exam skills
Paper structures & tips
Track your progress with spaced repetition
Sign up free — Aimnova tells you exactly which cards to review and when, so you remember everything before your IB exam.
Start Free