Proof by induction, contradiction and counterexample
In a minute
Three ways to prove or disprove a statement. proves a statement for every positive integer: show the first case, then show each case leads to the next. assumes the statement is false and reaches something impossible. A is one case that shows a statement is false, with the reason why.
You'll be able to
- Prove a statement for every positive integer by , with the basis, assumption, inductive step and conclusion written out.
- Use induction for sums, divisibility, repeated derivatives and powers of complex numbers.
- Prove a statement by , including that is irrational and that there are infinitely many primes.
- Disprove a statement with a , and explain why your example breaks it.
Before you start3 quick questions on what this builds on
Revise first: 1.2 Arithmetic sequences and series and 1.6 Elementary deductive proof
Proof by induction
Add up the first few odd numbers: , , and . Every total is a square number. So you might guess that the first odd numbers add up to .
Checking more cases never proves it: there are infinitely many positive integers to try.
Think of a ladder instead. Suppose you can step onto the first rung. Suppose also that from any rung you can always reach the next one. Then you can climb as high as you like. Induction turns this idea into a proof.
is a name for the statement, such as ''. is the set of positive integers
Every induction proof has four parts. Write all four, and label them.
1. Basis. Show that is true. Work out the two sides separately and show they are equal.
2. Assumption. Assume that is true for some . Write out the statement with in place of .
3. Inductive step. Use the assumption to show that is true. Write down what you are aiming for before you start.
4. Conclusion. Say that is true, and that true implies true. So is true for all by mathematical induction.
Some statements start at another value, such as . Then the basis checks that first value instead, , and the conclusion says 'for all '.
Try it first, then reveal one step at a time.
- Basis. When , the LHS is just the first term, . The RHS is . They are equal, so is true.
- Assumption. Assume is true for some , that is .
- Aim. You want : . The new last term is .
- Inductive step. Start from the LHS of . The first terms add up to by the assumption, so .
- Factorise: . So if is true, then is true.
- Conclusion. is true, and true implies true. So is true for all by mathematical induction.
With , the inductive step always starts the same way. The sum of terms is the sum of the first terms plus the th term.
Try it first, then reveal one step at a time.
- Basis. When : and . So is true.
- Assumption. Assume is true for some : .
- Aim. Put into the RHS. You want .
- Split off the last term. Putting into gives . So by the assumption, .
- Take out the common factor , writing everything over : .
- Factorise the quadratic: . The sum is , which is the aim. So true implies true.
- Conclusion. is true, and true implies true. So the result holds for all by mathematical induction.
Induction for divisibility, derivatives and complex numbers
The four parts never change. Only the inductive step does, and its job is always the same: write the case in terms of the case, then use the assumption.
For divisibility, turn the assumption into an equation. 'This expression is divisible by ' means it equals for some integer . Rearrange that equation so you can substitute it.
Try it first, then reveal one step at a time.
- Basis. When : , which is divisible by . So is true.
- Assumption. Assume is true for some : for some . Rearranged, .
- Inductive step. Write the case with one factor of split off: .
- Replace using the assumption: .
- Take out the : . As and are integers, is an integer. So is divisible by , and is true.
- Quick check with , so : and .
- Conclusion. is true, and true implies true. So is divisible by for all , by mathematical induction.
For derivatives, the statement is a formula for , the th of (see 5.12). The inductive step is one more differentiation.
Try it first, then reveal one step at a time.
- Basis. By the product rule, . The formula with gives . They agree, so is true.
- Assumption. Assume is true for some : .
- Aim. Put into the formula. You want .
- Inductive step. is the derivative of . The constant stays in front. The product rule on gives .
- Take out the common factor : . This is the aim, so is true.
- Conclusion. is true, and true implies true. So the formula holds for all by mathematical induction.
With complex numbers, induction often proves a rule for powers. The best known is De Moivre's theorem, proved by induction in 1.14. Here is a shorter one about the .
Try it first, then reveal one step at a time.
- A fact you need: for complex numbers and , .
- And , using . This is the conjugate of , so .
- Basis. When , both sides are . So is true.
- Assumption. Assume is true for some : .
- Inductive step. by the assumption. The fact with and turns this into . So is true.
- Conclusion. is true, and true implies true. So for all by mathematical induction. As , this says the conjugate of is .
Proof by contradiction
Sometimes you can't build a result directly. Instead, suppose it is false and follow where that leads. If you reach something impossible, the supposition was wrong. So the result is true.
Begin with 'Assume, for a contradiction, that …' and state exactly what you assume. End by naming the contradiction and saying what it proves.
Try it first, then reveal one step at a time.
- Assume, for a contradiction, that there are integers and with .
- Factorise the LHS: .
- and are integers, so is an integer. So the LHS is a multiple of .
- But , so is not a multiple of . A multiple of can't equal .
- This contradiction shows the assumption is false. So there are no integers and with .
The most famous proofs by contradiction are about . A rational number can be written as , with and .
You can always cancel such a fraction until and have no common factor except . The fraction is then in lowest terms.
The same is true with replaced by any prime, such as or . It also works for cubes: if a prime is a factor of , it is a factor of .
Try it first, then reveal one step at a time.
- Assume, for a contradiction, that is rational. Then , where , and the fraction is in lowest terms.
- Square both sides and multiply by : . So is a multiple of , and by the result above, so is .
- Write for some . Then , so . Dividing by gives .
- So is a multiple of , and by the same result, so is .
- Now and share the factor . This contradicts the fraction being in lowest terms. So is irrational.
Euclid's proof that the primes never run out is also a proof by contradiction.
1. Assume, for a contradiction, that there are only finitely many primes. Call them .
2. Let . is greater than , so it has at least one prime factor.
3. Dividing by any on the list leaves remainder . So no prime on the list is a factor of .
4. So has a prime factor that is not on the list. This contradicts the list holding every prime. So there are infinitely many primes.
itself need not be prime. For example, . Its prime factors, and , are simply not on the list.
Disproving with a counterexample
A statement that claims something for every case is false if it fails even once. So to disprove it, you need just one case where it fails.
Try it first, then reveal one step at a time.
- Try small values: give , all prime. Testing one at a time is slow, so look for a value that builds in a factor.
- Write . If , then , so every term has the factor .
- Calculate: .
- has the factor , which is neither nor , so is not prime. As , the statement fails for . So it is false.
Try it first, then reveal one step at a time.
- Write down what you graph: and for . The calculator finds the intersections at and .
- Between these values the cubic is above the exponential. So any between them should break the statement. Pick an easy one: .
- Work out both sides at : and .
- So . Since , the claim fails at , so the statement is false.
Common mistakes
- Writing 'let ' as the assumption. Write 'Assume the result is true for ', then the full statement with in place of .
- Checking the basis on one side only. At , work out the LHS and the RHS separately and show they are equal.
- Getting the new term wrong. Substitute into the general term with care: for it is .
- A conclusion without its reasons. Say the result is true for , and that true for implies true for , so it is true for all .
- Testing a few numbers instead of proving. Checking cases proves nothing in general, in induction or in contradiction, so argue with letters.
- Giving a counterexample with no reason. Show the calculation, then say why it makes the statement false.
Exam tips
- Prove by induction: each of the four parts earns marks, and the conclusion earns a reasoning (R) mark. Write the full concluding sentence even if the inductive step went wrong.
- Prove by contradiction: start with 'Assume, for a contradiction, that …', and finish by naming what is contradicted. Examiners look for both.
- Most induction questions are on Paper 1, so practise the algebra of the inductive step without a calculator.
Key takeaways
Practise this
16 past-paper questions on 1.15 in the AA HL bank, each with a mark scheme and a worked explanation.