This whole subtopic is higher level. Nothing in it is on an SL paper.
Educerie · IB Diploma · Mathematics: analysis and approaches
Topic 1 Number and algebra · 1.15 Proof by induction, contradiction and counterexample
What you must be able to do
| You must be able to | Level | What it looks like in the exam |
|---|---|---|
| Lay out a proof by mathematical induction in four parts: base case, assumption, inductive step, conclusion | HL only | Every induction question; each part carries marks |
| Prove results about sums of sequences by induction | HL only | "Prove by induction that ∑ r² = n(n + 1)(2n + 1)/6" (7 marks) |
| Prove divisibility results by induction | HL only | "Prove that 9ⁿ − 1 is divisible by 8 for all n ∈ ℤ⁺" (6 marks) |
| Prove results about derivatives (and complex numbers) by induction | HL only | "Prove that the nth derivative of xe^(2x) is…" (7 marks); De Moivre's theorem (1.14) |
| Prove a statement by contradiction, including irrationality and Euclid's proof that there are infinitely many primes | HL only | "Prove by contradiction that ∛5 is irrational" (5 marks) |
| Show that a statement is not always true by giving a counterexample and explaining why it is one | HL only | "Show that not all numbers of the form n² + 41n + 41 are prime" (3 marks) |
Before you start
You need the deductive proof of 1.6: an identity shown by a chain from one side to the other, with ≡ and "LHS = … = RHS". You need sigma notation from 1.2, the laws of indices, factorising, and, for the calculus example, the product rule and the derivative of eˣ from Topic 5. The words rational (a fraction p/q of integers with q ≠ 0) and irrational (not rational) must be clear, and you should know that every integer greater than 1 has a prime factor.
1The idea in one paragraph
A formula that works for n = 1, 2, 3, …, 100 has not been proved: the hundred-and-first case could fail. This subtopic gives three ways to settle a claim for good. Mathematical induction proves a statement for every positive integer by proving two things: that it is true for the first case, and that whenever it is true for one case it is true for the next. Proof by contradiction assumes the statement is false and follows the consequences until they become impossible, which shows the assumption was wrong. Proof by counterexample goes the other way: to show that a claim of the form "always" is false, one example where it fails is enough, provided you explain why it fails. In each, the marks are for the reasoning written down, not for the idea in your head.
2Induction: why two facts are enough
Think of an infinite row of dominoes, as in Figure 1. You want to be sure every one falls. You do not need to watch each one. You need two facts: the first domino falls, and whenever any domino falls, it knocks over the next one. Then the first knocks the second, the second the third, and so on for ever.
Mathematical induction is the same argument. Let P(n) be a statement about the positive integer n.
If P(1) is true, and P(k) true implies P(k + 1) true for every k ∈ ℤ⁺, then P(n) is true for all n ∈ ℤ⁺.
Neither fact is enough alone. The step without a base case proves nothing: "if 3ⁿ is even then 3ⁿ⁺¹ is even" is a correct implication about a statement that is never true. A base case without a step is just one example.
The layout. Figure 2 sets out the four parts. An IB mark scheme awards marks to each: typically one for the base case, one for the assumption, several for the algebra of the step, and a reasoning mark for the conclusion, which is only available if the earlier parts are in place.
- Base case. Show P(1) is true, by calculating both sides separately. "True for n = 1" with no working earns nothing.
- Assumption. "Assume P(k) is true for some k ∈ ℤ⁺", then write P(k) out in full. "Assume true for all k" assumes what you are trying to prove.
- Inductive step. Work on P(k + 1), use the assumption at a clearly visible point, and reach exactly the form P(k + 1) requires. Write the target down first so you know where you are going.
- Conclusion. A sentence such as: "P(1) is true, and P(k) true implies P(k + 1) true, so by the principle of mathematical induction P(n) is true for all n ∈ ℤ⁺."
The guide notes an important contrast for TOK. In science, "induction" means generalizing from many observations, which can always be overturned by the next one. Mathematical induction is not that at all: it is a deductive proof, and it is certain.
3Induction on sums
Figure 3 shows why 1 + 3 + 5 + 7 = 16 = 4²: each odd number is an L-shaped layer that enlarges the square by one. It suggests that the sum of the first n odd numbers is n². The picture is persuasive, and induction turns it into a proof. For sums, the step always has the same shape: the sum to k + 1 terms is the sum to k terms plus the (k + 1)th term, and the assumption replaces the sum to k terms.
Worked example 1. Prove by induction that ∑ r(r + 1), from r = 1 to n, equals n(n + 1)(n + 2)/3 for all n ∈ ℤ⁺.
Conclusion. P(1) is true, and P(k) true implies P(k + 1) true. So P(n) is true for all n ∈ ℤ⁺ by mathematical induction.
The move that saves time is taking out the common factor (k + 1)(k + 2) at once. Expanding everything into a cubic and then trying to factorise it back is slower and invites errors.
4Induction on divisibility
"f(n) is divisible by 4" means f(n) = 4m for some integer m. Write that down in the assumption: it gives you something to substitute.
Worked example 2. Prove by induction that 5ⁿ + 3 is divisible by 4 for all n ∈ ℤ⁺.
Conclusion. P(1) is true, and P(k) true implies P(k + 1) true, so 5ⁿ + 3 is divisible by 4 for all n ∈ ℤ⁺, by mathematical induction.
The phrase "5m − 3 is an integer" is not decoration. Divisibility by 4 means 4 times an integer, so say so. An alternative route is to show that f(k + 1) − f(k) is divisible by 4: here 5ᵏ⁺¹ − 5ᵏ = 4 × 5ᵏ, so f(k + 1) = f(k) + 4 × 5ᵏ, a sum of two multiples of 4.
5Induction with derivatives, and elsewhere
The guide lists differentiation and complex numbers as places induction appears. The step is the same idea: the statement for k + 1 comes from the statement for k by one more operation, here one more differentiation.
Worked example 3. Prove by induction that dⁿ/dxⁿ (xeˣ) = (x + n)eˣ for all n ∈ ℤ⁺.
Conclusion as before. The key line is the second: the (k + 1)th derivative is the derivative of the kth, which is where the assumption goes in.
The proof of De Moivre's theorem in 1.14 is the same pattern with complex numbers: (cos θ + i sin θ)ᵏ⁺¹ = (cos θ + i sin θ)ᵏ(cos θ + i sin θ), then the assumption, then the compound angle formulae.
A base case other than 1. Some statements start later, "for all integers n ≥ 4" or "for n ∈ ℕ", starting at 0. Then the base case is the first value in the set, and the assumption and conclusion say k ≥ 4 or k ∈ ℕ to match.
6Proof by contradiction
Some statements say that something is impossible: no fraction equals √3; there is no largest prime. You cannot check every fraction. Instead:
Proof by contradiction: assume the statement is false; reason correctly from that assumption; reach something impossible; conclude that the assumption was false, so the statement is true.
Figure 4 shows the shape. The impossible thing is often a direct clash with a condition you set at the start, such as "in lowest terms".
Worked example 4. Prove by contradiction that √3 is irrational.
First a fact you will use: if p² is divisible by 3, then p is divisible by 3. Every integer is 3m, 3m + 1 or 3m + 2. Squaring the last two gives 9m² + 6m + 1 = 3(3m² + 2m) + 1 and 9m² + 12m + 4 = 3(3m² + 4m + 1) + 1, both one more than a multiple of 3. So only a multiple of 3 has a square divisible by 3.
Conclusion. The assumption that √3 is rational leads to a contradiction, so √3 is irrational.
The guide mentions the Pythagoreans, who found that √2 is irrational, the same proof with 2 in place of 3. For ∛5 the argument is identical in shape: p³ = 5q³, so 5 divides p³, so 5 divides p (because 5 is prime); then p = 5m gives q³ = 25m³, so 5 divides q too, contradicting lowest terms.
Worked example 5. Prove by contradiction that if a is rational and b is irrational, then a + b is irrational.
Conclusion. So a + b is irrational. The whole proof rests on one fact: the difference of two rational numbers is rational.
Euclid's proof that there are infinitely many primes. This is one of the oldest proofs in mathematics, and the guide names it.
Worked example 6. Prove by contradiction that there are infinitely many prime numbers.
Conclusion. So there are infinitely many primes.
A common mistake is to say "N is a new prime". It need not be. Figure 5 shows that 2 × 3 × 5 × 7 × 11 × 13 + 1 = 30 031 = 59 × 509, which is not prime; but its prime factors, 59 and 509, are missing from the list, and that is all the proof needs.
7Counterexamples
To prove "always", you need a proof. To disprove "always", you need one case where the statement fails: a counterexample. The guide is explicit that it is not sufficient to state the counterexample alone: you must show the working that proves it fails.
Worked example 7. Show that not every number of the form n² + 41n + 41, n ∈ ℕ, is prime.
Try small values, as Figure 6 does. n = 0, 1, 2, 3 give 41, 83, 127, 173, all prime. n = 4 gives 16 + 164 + 41 = 221 = 13 × 17. So 221 is a value of n² + 41n + 41 that is not prime, and the statement "every such number is prime" is false. Without "= 13 × 17" the answer earns nothing: the examiner needs to see why 221 fails.
A counterexample can also be found by thinking rather than searching. n = 41 gives 41² + 41 × 41 + 41 = 41(41 + 41 + 1) = 41 × 83, which is plainly not prime.
Worked example 8. Show that the statement "there are no positive integer solutions to x² + y² = 10" is not always true.
x = 1, y = 3: 1² + 3² = 1 + 9 = 10. So (1, 3) is a positive integer solution, and the statement is false.
Notice the logic: the first four values of n² + 41n + 41 being prime proved nothing, while the single value 221 settled the question. Examples cannot prove a general statement; one counterexample can destroy it.
TOK and the mathematical community. The guide asks who decides that a proof is valid. The four-colour theorem (any map can be coloured with four colours so that neighbouring regions differ) was proved in 1976 with a computer checking a very large number of cases no person could check by hand. It was accepted only after years of scrutiny, and the argument about whether a proof nobody can read counts as a proof is a good essay topic.
8Choosing the method
| The statement says… | Use |
|---|---|
| something holds for every positive integer n (a sum, a divisibility, an nth derivative, a power) | induction |
| something is impossible, irrational, or there are infinitely many of something | contradiction |
| something is "always" true, and you suspect it is not | counterexample, with the check shown |
| an identity holds for all x | direct deductive proof (1.6) |
9Where marks are lost
A base case asserted, not shown. Calculate both sides for n = 1 and show they are equal.
"Assume true for all k". That assumes the result. Write "for some k ∈ ℤ⁺".
Not using the assumption, or hiding where it is used. Mark the line: "by the assumption". A step that never uses P(k) is not an induction proof.
Working backwards from P(k + 1) as if it were true. Start from one side of P(k + 1) and reach the other. Do not start by writing P(k + 1) as an equation and manipulate both sides.
No conclusion, or a conclusion with no content. The final R mark needs the sentence: P(1) true, P(k) ⇒ P(k + 1), therefore true for all n ∈ ℤ⁺.
Forgetting "lowest terms" in an irrationality proof. Without it, "p and q are both divisible by 3" contradicts nothing.
Claiming Euclid's N is prime. N need not be prime. The contradiction comes from its prime factors, which are not on the list.
A counterexample with no check. "n = 4" alone scores nothing. Show 221 = 13 × 17.
10Work it right
- Choose the method from the table in section 8 before writing anything.
- For induction, define P(n) in words or as the equation, then write the four parts with their labels: base case, assumption, inductive step, conclusion.
- In the step, write the target P(k + 1) first, then start from its left-hand side and reach its right-hand side.
- For sums, split off the last term; for divisibility, write f(k) = am with m an integer; for derivatives, differentiate the kth derivative once more.
- Take out common factors early; do not expand what you are about to factorise.
- For contradiction, state the assumption explicitly (with "lowest terms" where relevant), reason step by step, name the contradiction, then conclude.
- For a counterexample, give the value, show the calculation, and say which part of the statement fails.
11Try it
Marks in brackets. These can appear on any paper; none needs a calculator.
Q1. Prove by mathematical induction that ∑ r², from r = 1 to n, equals n(n + 1)(2n + 1)/6 for all n ∈ ℤ⁺. 7 marks
Q2. Prove by mathematical induction that 9ⁿ − 1 is divisible by 8 for all n ∈ ℤ⁺. 6 marks
Q3. Let f(x) = xe^(2x). Prove by mathematical induction that the nth derivative of f is f⁽ⁿ⁾(x) = 2ⁿ⁻¹(2x + n)e^(2x) for all n ∈ ℤ⁺. 7 marks
Q4. Prove by contradiction that log₂ 3 is irrational. 5 marks
Q5. A student claims that n² − n + 11 is prime for every positive integer n. Show that the claim is false. 3 marks
Q6. Prove by contradiction that if a is a non-zero rational number and b is irrational, then ab is irrational. 4 marks
12In one breath
Examples never prove "always"; three methods do the job. Induction proves a statement P(n) for every positive integer: show P(1) by working out both sides, assume P(k) for some k ∈ ℤ⁺, use that assumption visibly to prove P(k + 1), and conclude in a sentence that P(n) is true for all n; for sums split off the last term, for divisibility write f(k) = am with m an integer, for derivatives differentiate once more, and for De Moivre multiply by one more cis θ. Contradiction proves impossibility: assume the opposite (√3 = p/q in lowest terms; finitely many primes; a + b rational), reason to something impossible, and conclude the assumption was false; Euclid's N = p₁p₂…pₙ + 1 has a prime factor not on the list, though N itself need not be prime. A counterexample disproves "always" with one case, and the working that shows it fails is compulsory: n = 4 gives 221 = 13 × 17.
Answers
Q1. Base case: n = 1, LHS = 1, RHS = 1 × 2 × 3/6 = 1, so true. Assume ∑ r² to k = k(k + 1)(2k + 1)/6 for some k ∈ ℤ⁺. Then ∑ r² to k + 1 = k(k + 1)(2k + 1)/6 + (k + 1)² = (k + 1)/6 × [k(2k + 1) + 6(k + 1)] = (k + 1)/6 × (2k² + 7k + 6) = (k + 1)(k + 2)(2k + 3)/6, which is the formula with n = k + 1, since (k + 1)((k + 1) + 1)(2(k + 1) + 1)/6 = (k + 1)(k + 2)(2k + 3)/6. So P(k + 1) is true. P(1) is true and P(k) ⇒ P(k + 1), so P(n) is true for all n ∈ ℤ⁺ by induction. A1 for the base case with both sides shown, M1 for the assumption stated for some k, M1 for adding the (k + 1)th term (k + 1)², M1 for taking out (k + 1), A1 for 2k² + 7k + 6, A1 for (k + 1)(k + 2)(2k + 3)/6, R1 for the conclusion (only if the first two M marks are earned).
Q2. Base case: 9 − 1 = 8, divisible by 8. Assume 9ᵏ − 1 = 8m for some k ∈ ℤ⁺ and m ∈ ℤ. Then 9ᵏ⁺¹ − 1 = 9 × 9ᵏ − 1 = 9(8m + 1) − 1 = 72m + 8 = 8(9m + 1), and 9m + 1 is an integer, so 9ᵏ⁺¹ − 1 is divisible by 8. P(1) true and P(k) ⇒ P(k + 1), so true for all n ∈ ℤ⁺ by induction. A1 base case, M1 assumption written as 9ᵏ − 1 = 8m, M1 for writing 9ᵏ⁺¹ as 9 × 9ᵏ and substituting, A1 for 8(9m + 1), A1 for stating 9m + 1 is an integer, R1 conclusion.
Q3. Base case: f′(x) = e^(2x) + 2xe^(2x) = (2x + 1)e^(2x), and 2⁰(2x + 1)e^(2x) = (2x + 1)e^(2x), so true. Assume f⁽ᵏ⁾(x) = 2ᵏ⁻¹(2x + k)e^(2x) for some k ∈ ℤ⁺. Then f⁽ᵏ⁺¹⁾(x) = d/dx[2ᵏ⁻¹(2x + k)e^(2x)] = 2ᵏ⁻¹[2e^(2x) + 2(2x + k)e^(2x)] = 2ᵏ(1 + 2x + k)e^(2x) = 2ᵏ(2x + (k + 1))e^(2x), which is the formula with n = k + 1. Conclusion as usual. A1 base case using the product rule, M1 assumption, M1 for differentiating the kth derivative, A1 for the product rule applied correctly, A1 for taking out 2ᵏ, A1 for 2ᵏ(2x + k + 1)e^(2x), R1 conclusion.
Q4. Assume log₂ 3 is rational: log₂ 3 = p/q with p, q positive integers (log₂ 3 > 0). Then 2^(p/q) = 3, so 2ᵖ = 3^q. The left side is even (p ≥ 1) and the right side is odd, which is impossible. So log₂ 3 is irrational. M1 for assuming log₂ 3 = p/q, M1 for converting to 2ᵖ = 3^q, A1 for that equation, R1 for even ≠ odd, R1 for the conclusion.
Q5. n = 11: 11² − 11 + 11 = 121 = 11 × 11, which is not prime. So the claim is false. A1 for a valid value of n, A1 for evaluating it, R1 for showing it is not prime (the factorisation) and concluding. Any correct counterexample scores full marks; n = 11 is the smallest.
Q6. Assume ab is rational: ab = r/s with r, s ∈ ℤ, s ≠ 0. a = p/q with p, q ∈ ℤ, p ≠ 0, q ≠ 0. Then b = ab ÷ a = (r/s) × (q/p) = rq/(sp), with sp ≠ 0, so b is rational, contradicting b irrational. So ab is irrational. M1 for the assumption, M1 for writing b = ab/a, A1 for rq/(sp) with sp ≠ 0 (this needs a ≠ 0), R1 for the contradiction and conclusion.
Educerie · written from the published IB Diploma Programme Mathematics: analysis and approaches guide, first assessment 2021, section AHL 1.15 Proof by mathematical induction, proof by contradiction, use of a counterexample. Original text, examples and questions. Diagrams drawn by Educerie. Last reviewed 25 September 2026.