This note covers three ways of establishing mathematical statements: proof by induction, proof by contradiction and disproof by counterexample. Each has a fixed structure that you can learn. Writing the structure clearly is as important as the algebra inside it.
Key ideas
A proof shows that a statement is true in every case, not just in the cases you tried. A single example never proves a general claim, but a single counterexample can disprove one.
Proof by induction is used for statements about all positive integers \(n\), such as a formula for a sum or a divisibility claim. Picture a long line of dominoes. If the first falls, and each one knocks over the next, then they all fall. The proof has four parts.
- Base case. Show that the statement is true for the first value, usually \(n=1\).
- Assumption. Assume the statement is true for \(n=k\), where \(k\) is some positive integer.
- Inductive step. Use the assumption to show that the statement is true for \(n=k+1\).
- Conclusion. State that the statement is true for \(n=1\), and that if it is true for \(n=k\) then it is true for \(n=k+1\), so by mathematical induction it is true for all positive integers \(n\).
In the inductive step, aim at the target. Write down what the statement says for \(k+1\), and make your working head towards it. For a sum, add the next term to the assumed formula. For a divisibility claim, rewrite the expression for \(k+1\) so that it contains the expression for \(k\) plus something obviously divisible.
Proof by contradiction. Assume that the statement you want to prove is false. Follow the logic carefully until you reach something impossible, such as a number being both odd and even. Since correct reasoning cannot produce a contradiction, the assumption must have been wrong, so the original statement is true. This method is often used to show that something does not exist, or that a number is irrational.
Disproof by counterexample. To show that a claim for all cases is false, you only need one case where it fails. State the case, show the calculation, and say clearly that the claim is therefore false. A counterexample must satisfy the conditions of the claim.
Definitions and formulae
| Term or formula | Meaning / when to use |
|---|---|
| Induction | Proves a statement for all integers \(n\ge n_0\). It needs a base case and an inductive step. |
| Inductive hypothesis | The assumption that the statement holds for \(n=k\). |
| Contradiction | Assume the opposite, derive an impossibility, and conclude the original statement is true. |
| Counterexample | One case that makes a "for all" claim false. |
| \(\displaystyle\sum_{r=1}^{n}r(r+1)=\frac{n(n+1)(n+2)}3\) | The sum used in Example 1. |
| An integer \(m\) is a multiple of 6 if \(m=6t\) for some integer \(t\) | How to write divisibility in an induction proof. |
Worked examples
Example 1 Prove by induction that \(1\times2+2\times3+\cdots+n(n+1)=\dfrac{n(n+1)(n+2)}3\) for all positive integers \(n\).
Base case. For \(n=1\), the left side is \(1\times2=2\). The right side is \(\dfrac{1\times2\times3}3=2\). They agree, so the statement is true for \(n=1\).
Assumption. Assume that for some positive integer \(k\), \(1\times2+\cdots+k(k+1)=\dfrac{k(k+1)(k+2)}3\).
Inductive step. For \(n=k+1\), add the next term \((k+1)(k+2)\) to both sides:
\(1\times2+\cdots+(k+1)(k+2)=\dfrac{k(k+1)(k+2)}3+(k+1)(k+2)\)
Factor out \((k+1)(k+2)\): \(=(k+1)(k+2)\left(\dfrac k3+1\right)=(k+1)(k+2)\dfrac{k+3}3\).
This is \(\dfrac{(k+1)(k+2)(k+3)}3\), which is the formula with \(n=k+1\).
Conclusion. The statement is true for \(n=1\), and if it is true for \(n=k\) then it is true for \(n=k+1\). By mathematical induction it is true for all positive integers \(n\).
Answer: proved
Example 2 Prove by induction that \(7^n-1\) is divisible by 6 for all positive integers \(n\).
Base case. For \(n=1\), \(7^1-1=6\), which is divisible by 6.
Assumption. Assume \(7^k-1=6t\) for some integer \(t\). Then \(7^k=6t+1\).
Inductive step. \(7^{k+1}-1=7\times7^k-1=7(6t+1)-1=42t+6=6(7t+1)\).
Since \(7t+1\) is an integer, \(7^{k+1}-1\) is divisible by 6.
Conclusion. True for \(n=1\), and true for \(n=k\) implies true for \(n=k+1\), so by induction \(7^n-1\) is divisible by 6 for all positive integers \(n\).
Answer: proved
Example 3 (a) Prove by contradiction that \(\sqrt3\) is irrational. (b) Show by counterexample that "\(n^2+n+41\) is prime for every positive integer \(n\)" is false.
(a) Assume \(\sqrt3\) is rational. Then \(\sqrt3=\dfrac pq\), where \(p\) and \(q\) are integers with no common factor, and \(q\ne0\).
Square both sides: \(3=\dfrac{p^2}{q^2}\), so \(p^2=3q^2\). Hence \(p^2\) is a multiple of 3.
If \(p\) were not a multiple of 3, then \(p=3m\pm1\) and \(p^2=9m^2\pm6m+1\), which leaves remainder 1 on division by 3. So \(p\) must be a multiple of 3. Write \(p=3s\).
Then \(9s^2=3q^2\), so \(q^2=3s^2\). By the same argument, \(q\) is a multiple of 3.
Now \(p\) and \(q\) share the factor 3, which contradicts the assumption that they have no common factor. So \(\sqrt3\) is irrational.
(b) Try \(n=40\): \(40^2+40+41=1600+40+41=1681=41\times41\). This is not prime, so the claim is false.
Answer: (a) \(\sqrt3\) is irrational. (b) \(n=40\) is a counterexample.
Common errors
- Skipping the base case. Without it the dominoes are never started, and the proof is incomplete.
- Writing "assume it is true for all \(n\)" in the assumption. You assume it for one value, \(n=k\), and nothing more.
- Using the formula for \(n=k+1\) at the start of the inductive step. That assumes what you are trying to prove. Start from the assumption and arrive at it.
- Leaving out the final conclusion sentence, or not mentioning both the base case and the inductive step in it.
- In a contradiction proof, not stating what the contradiction is, or assuming the wrong thing. You must assume the exact opposite of the claim.
Exam tip: Write the required statement for \(n=k+1\) at the side of the page before starting the inductive step. It tells you exactly where the algebra must end.
Check yourself
- Outline an induction proof that \(1+3+5+\cdots+(2n-1)=n^2\).
Answer
Base case: for \(n=1\) the left side is 1 and the right side is \(1^2=1\). Assume \(1+3+\cdots+(2k-1)=k^2\). Add the next term \(2k+1\): \(k^2+2k+1=(k+1)^2\), which is the statement for \(n=k+1\). Conclude by induction. - Show by counterexample that "\(2^n\gt n^2\) for all positive integers \(n\)" is false.
Answer
For \(n=2\): \(2^2=4\) and \(2^2=4\), so \(2^n\gt n^2\) fails because they are equal. (Also \(n=3\): \(8\lt9\).) One failing value is enough. - Prove by contradiction that if \(n^2\) is odd, then \(n\) is odd.
Answer
Assume \(n^2\) is odd but \(n\) is even. Then \(n=2m\), so \(n^2=4m^2=2(2m^2)\), which is even. This contradicts \(n^2\) being odd, so \(n\) must be odd. - In an induction proof that \(3^n\gt2n\) for \(n\ge1\), the assumption is \(3^k\gt2k\). Show the inductive step.
Answer
\(3^{k+1}=3\times3^k\gt3\times2k=6k\). Since \(k\ge1\), \(6k=2k+4k\ge2k+4\gt2k+2\). So \(3^{k+1}\gt2(k+1)\). The base case \(n=1\) gives \(3\gt2\), so the statement holds for all \(n\ge1\).