Practice Flashcards
What 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 Flashcards in Topic 1.15
Below are all 24 flashcards for this topic. Sign up free to track your progress and get personalized review schedules.
1.15.18 cards
What are the four steps of proof by induction?
Base case (n = 1), assume true for n = k, prove true for n = k + 1, conclude true for all n.
What's the domino analogy for induction?
Knock the first domino (base case) and show each knocks the next (k ⇒ k + 1), so they all fall (all n).
What must the inductive step USE?
The assumption (the result for n = k) — that's the link that proves n = k + 1.
How do you finish an induction proof?
State the conclusion: true for n = 1 and 'true for k ⇒ true for k + 1', so true for all n ∈ ℤ⁺.
Base case for 1 + 2 + … + n = n(n+1)/2?
n = 1: LHS = 1, RHS = 1(2)/2 = 1 ✓.
In a divisibility induction, the key move in the step?
Rewrite the (k+1) expression so the assumption (e.g. 6ᵏ − 1 = 5m) appears, then factor out the divisor.
Why is the base case essential?
Without a true starting case, the chain k ⇒ k + 1 never gets going — nothing is ever shown true.
What does 'assume true for n = k' mean?
Take the statement as given for one (unspecified) value k, so you can use it to prove the next case.
1.15.28 cards
How does proof by contradiction work?
Assume the statement is false, derive something impossible (a contradiction), so the assumption is wrong and the statement is true.
What do you assume at the start of a contradiction proof?
The negation (opposite) of what you want to prove.
What does reaching a contradiction prove?
That the assumption (the opposite) is false — so the original statement is true.
Outline the proof that √2 is irrational.
Assume √2 = p/q in lowest terms; show p² = 2q² makes both p and q even, contradicting 'no common factor'.
How do you prove 'if n² is even then n is even' by contradiction?
Assume n is odd (n = 2k+1); then n² = 2(2k²+2k)+1 is odd, contradicting n² even.
Prove the sum of a rational and an irrational is irrational — the contradiction?
Assuming r + x is rational forces x = (r + x) − r to be rational, contradicting x irrational.
How should you open a contradiction proof in an exam?
'Assume, for contradiction, that … [the negation].'
Is a contradiction a mistake?
No — it's the goal; it shows the assumption can't hold.
1.15.38 cards
What is a counterexample?
A single case where a 'for all' statement fails — enough to prove the statement false.
How many counterexamples disprove a universal statement?
Just one.
Where should you look for counterexamples?
Small numbers (0, 1), negatives, fractions, and edge cases.
Counterexample to 'all primes are odd'?
2 — it's prime and even.
Counterexample to 'a² = b² ⇒ a = b'?
a = 2, b = −2: 4 = 4 but 2 ≠ −2.
Counterexample to 'x² ≥ x for all real x'?
x = ½: ¼ < ½.
Counterexample to 'the sum of two irrationals is irrational'?
√2 + (−√2) = 0, which is rational.
What must you check about a counterexample?
That it meets the statement's condition (hypothesis) but breaks the conclusion.
Topic 1.15 study notes
Full notes & explanations for Proof by induction (HL only)
Math AA exam skills
Paper structures, command terms & tips
Want smart review reminders?
Sign up free to track your progress. Our spaced repetition algorithm will tell you exactly which cards to review and when.
Start Free