1.15 Proof by induction, contradiction and counterexample
Studying this course? Keep your progress in one place.
Key facts
- Induction: basis, assumption, inductive step, and a full conclusion.
- Induction works for sums, divisibility, derivatives and De Moivre.
- Contradiction: assume the opposite and reach an impossibility, such as a fraction not in lowest terms.
- Counterexample: one case disproves a "for all" claim, but you must show why it fails.
- Many examples that work never prove a universal claim.
Structure of induction
Show the basis, assume , prove , then state the full conclusion.
Mathematical induction proves for every . IB mark schemes award the final reasoning mark only if the basis and inductive step are both done properly, so always write the full conclusion.
Write "assume is true", not "let ": you are assuming, not setting a value. Write the target before the inductive step so you know what to aim for.
- 1
Basis
Show is true
- 2
Assumption
Assume is true for some
- 3
Inductive step
Using it, show is true
- 4
Conclusion
true and , so true for all by induction
Worked example
Prove that for all .
- 1
Basis: gives LHS and RHS .
- 2
Assume . Target: .
- 3
Add the th term: .
- 4
Conclude: true and , so true for all by induction.
Which is the correct way to start the inductive step?
Induction in context
Sums, divisibility, derivatives and De Moivre all follow the same pattern.
In each case assume , then rewrite in terms of it.
For a sum, add the th term and factorise. For divisibility, rewrite the assumption (for example ) and substitute. For a derivative, differentiate the assumed th derivative, for example . For De Moivre, multiply by .
- 1
Base case
show P(1) is true
- 2
Assume P(k)
for some positive integer k
- 3
Rewrite P(k + 1)
in terms of P(k): add a term, substitute or differentiate
- 4
Conclude
true for n = 1, and P(k) ⇒ P(k+1), so true for all positive integers n
Sums
- Add the th term
- Then factorise
Divisibility
- Assume a multiple
- Rewrite using it
Derivatives
- Differentiate the assumed form
De Moivre
- Multiply by
- Compound angle identities
Worked example
Show that is divisible by 4 for all .
- 1
Basis: , divisible by 4.
- 2
Assume , so .
- 3
.
- 4
Divisible by 4, so ; with true, true for all by induction.
To show is divisible by 6, assume . What is ?
Proof by contradiction
Assume the statement is false and show this leads to something impossible.
For : assume in lowest terms. Then , so 5 divides ; write , giving , so 5 divides . That contradicts lowest terms.
Euclid: assume finitely many primes . leaves remainder 1 on division by each, so it has a prime factor not in the list. need not be prime itself. Always state "in lowest terms" at the start.
- 1
Assume the opposite
Suppose the statement is false
- 2
Deduce
Follow logical steps from that
- 3
Impossibility
For example, a fraction both in and not in lowest terms
- 4
Conclude
The assumption was wrong, so the statement is true
In the proof that is irrational, where does the contradiction come from?
Counterexamples
One counterexample disproves a "for all" claim, but you must show why it breaks the claim.
A counterexample is a single case where the claim fails. Stating it alone is not enough: show why, for example by exhibiting a factorisation or evaluating both sides of an inequality.
Examples that work never prove a universal claim: is prime for yet fails at . Watch non-strict inequalities: satisfies , so it is not a counterexample to it.
- Many examples that workprove nothing
- One counterexampledisproves "for all"
Worked example
Disprove the claim that is prime for all .
- 1
Try : .
- 2
Factorise: .
- 3
It has factors other than 1 and itself.
Which value is a counterexample to " for all real "?
Try an exam question
Prove by induction that is divisible by 4 for all .
[4 marks]
- [1]Basis: gives , divisible by 4.
- [1]Assumes for some integer .
- [1]Shows .
- [1]Concludes: true for , and , so true for all by induction.
That's the notes covered.
Carry on to the next subtopic.
Try a question
Find the common value of both sides of when .
1 mark, marked against the mark scheme
Find the common value of both sides of when .
1 mark, marked against the mark scheme