1.15 · AHL · HL onlyPaper 1Paper 2Paper 3

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 3\sqrt{3} 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
Check yourself
Work out ∑r=14(3r−1)\sum_{r=1}^{4} (3r - 1).
Check yourself
Let n∈Zn \in \mathbb{Z}. Which line shows that 6n+156n + 15 is a multiple of 33?
Check yourself
Let n∈Zn \in \mathbb{Z}. Which line shows that (2n+1)2(2n + 1)^{2} is odd?

Revise first: 1.2 Arithmetic sequences and series and 1.6 Elementary deductive proof

Proof by induction

Add up the first few odd numbers: 1=11 = 1, 1+3=41 + 3 = 4, 1+3+5=91 + 3 + 5 = 9 and 1+3+5+7=161 + 3 + 5 + 7 = 16. Every total is a square number. So you might guess that the first nn odd numbers add up to n2n^{2}.

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.

P(n)P(n) is a name for the statement, such as '1+3+⋯+(2n−1)=n21 + 3 + \cdots + (2n - 1) = n^{2}'. Z+\mathbb{Z}^{+} is the set of positive integers 1,2,3,…1, 2, 3, \ldots

Every induction proof has four parts. Write all four, and label them.

1. Basis. Show that P(1)P(1) is true. Work out the two sides separately and show they are equal.

2. Assumption. Assume that P(k)P(k) is true for some k∈Z+k \in \mathbb{Z}^{+}. Write out the statement with kk in place of nn.

3. Inductive step. Use the assumption to show that P(k+1)P(k + 1) is true. Write down what you are aiming for before you start.

4. Conclusion. Say that P(1)P(1) is true, and that P(k)P(k) true implies P(k+1)P(k + 1) true. So P(n)P(n) is true for all n∈Z+n \in \mathbb{Z}^{+} by mathematical induction.

Some statements start at another value, such as n≥2n \ge 2. Then the basis checks that first value instead, P(2)P(2), and the conclusion says 'for all n≥2n \ge 2'.

Worked exampleProve by mathematical induction that 1+3+5+⋯+(2n−1)=n21 + 3 + 5 + \cdots + (2n - 1) = n^{2}, that is ∑r=1n(2r−1)=n2\sum_{r=1}^{n} (2r - 1) = n^{2}, for all n∈Z+n \in \mathbb{Z}^{+}.

Try it first, then reveal one step at a time.

  1. Basis. When n=1n = 1, the LHS is just the first term, 11. The RHS is 12=11^{2} = 1. They are equal, so P(1)P(1) is true.

With , the inductive step always starts the same way. The sum of k+1k + 1 terms is the sum of the first kk terms plus the (k+1)(k + 1)th term.

Learn this
∑r=1k+1ur=∑r=1kur+uk+1\sum_{r=1}^{k+1} u_{r} = \sum_{r=1}^{k} u_{r} + u_{k+1}
Worked exampleProve by induction that ∑r=1nr(r+3)=n(n+1)(n+5)3\sum_{r=1}^{n} r(r + 3) = \frac{n(n + 1)(n + 5)}{3} for all n∈Z+n \in \mathbb{Z}^{+}.

Try it first, then reveal one step at a time.

  1. Basis. When n=1n = 1: LHS=1×4=4\text{LHS} = 1 \times 4 = 4 and RHS=1×2×63=4\text{RHS} = \frac{1 \times 2 \times 6}{3} = 4. So P(1)P(1) is true.
Check yourself
You want to prove that ∑r=1n1r(r+1)=nn+1\sum_{r=1}^{n} \frac{1}{r(r + 1)} = \frac{n}{n + 1} for all n∈Z+n \in \mathbb{Z}^{+}. Which term do you add to the sum of the first kk terms to get the sum of the first k+1k + 1 terms?
Check yourself
Continuing, the assumption gives ∑r=1k+11r(r+1)=kk+1+1(k+1)(k+2)\sum_{r=1}^{k+1} \frac{1}{r(r + 1)} = \frac{k}{k + 1} + \frac{1}{(k + 1)(k + 2)}. Simplify the right-hand side.

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 k+1k + 1 case in terms of the kk case, then use the assumption.

For divisibility, turn the assumption into an equation. 'This expression is divisible by 99' means it equals 9m9m for some integer mm. Rearrange that equation so you can substitute it.

Worked exampleUse mathematical induction to prove that 99 is a factor of 4n+6n−14^{n} + 6n - 1 for every n∈Z+n \in \mathbb{Z}^{+}.

Try it first, then reveal one step at a time.

  1. Basis. When n=1n = 1: 41+6×1−1=9=9×14^{1} + 6 \times 1 - 1 = 9 = 9 \times 1, which is divisible by 99. So P(1)P(1) is true.
Check yourself
To prove that 32n−13^{2n} - 1 is divisible by 88, you assume 32k−1=8m3^{2k} - 1 = 8m, where m∈Zm \in \mathbb{Z}. Which expression equals 32(k+1)−13^{2(k+1)} - 1?

For derivatives, the statement is a formula for f(n)(x)f^{(n)}(x), the nnth of ff (see 5.12). The inductive step is one more differentiation.

Worked exampleLet f(x)=xe2xf(x) = x\mathrm{e}^{2x}. Prove by induction that f(n)(x)=2n−1(2x+n)e2xf^{(n)}(x) = 2^{n-1}(2x + n)\mathrm{e}^{2x} for all n∈Z+n \in \mathbb{Z}^{+}.

Try it first, then reveal one step at a time.

  1. Basis. By the product rule, f′(x)=1⋅e2x+x⋅2e2x=(2x+1)e2xf'(x) = 1 \cdot \mathrm{e}^{2x} + x \cdot 2\mathrm{e}^{2x} = (2x + 1)\mathrm{e}^{2x}. The formula with n=1n = 1 gives 20(2x+1)e2x=(2x+1)e2x2^{0}(2x + 1)\mathrm{e}^{2x} = (2x + 1)\mathrm{e}^{2x}. They agree, so P(1)P(1) is true.
Check yourself
To prove that the nnth derivative of 1x\frac{1}{x} is (−1)nn!xn+1\frac{(-1)^{n}n!}{x^{n+1}}, you differentiate the n=kn = k case. Which is the derivative of (−1)kk!xk+1\frac{(-1)^{k}k!}{x^{k+1}} with respect to xx?

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 z∗z^{*}.

Worked exampleLet z=a+biz = a + b\mathrm{i}, where a,b∈Ra, b \in \mathbb{R}. Prove by induction that (z∗)n=(zn)∗(z^{*})^{n} = (z^{n})^{*} for all n∈Z+n \in \mathbb{Z}^{+}.

Try it first, then reveal one step at a time.

  1. A fact you need: for complex numbers v=p+qiv = p + q\mathrm{i} and w=s+tiw = s + t\mathrm{i}, vw=(ps−qt)+(pt+qs)ivw = (ps - qt) + (pt + qs)\mathrm{i}.

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.

Worked exampleProve by contradiction that there are no integers mm and nn such that 6m+9n=1006m + 9n = 100.

Try it first, then reveal one step at a time.

  1. Assume, for a contradiction, that there are integers mm and nn with 6m+9n=1006m + 9n = 100.

The most famous proofs by contradiction are about . A rational number can be written as pq\frac{p}{q}, with p,q∈Zp, q \in \mathbb{Z} and q≠0q \ne 0.

You can always cancel such a fraction until pp and qq have no common factor except 11. The fraction is then in lowest terms.

The same is true with 33 replaced by any prime, such as 22 or 55. It also works for cubes: if a prime is a factor of p3p^{3}, it is a factor of pp.

Worked exampleProve that 3\sqrt{3} is irrational.

Try it first, then reveal one step at a time.

  1. Assume, for a contradiction, that 3\sqrt{3} is rational. Then 3=pq\sqrt{3} = \frac{p}{q}, where p,q∈Zp, q \in \mathbb{Z}, q≠0q \ne 0 and the fraction is in lowest terms.
Check yourself
To prove that 53\sqrt[3]{5} is irrational, assume 53=pq\sqrt[3]{5} = \frac{p}{q} in lowest terms. Cubing gives p3=5q3p^{3} = 5q^{3}, so p=5mp = 5m for some m∈Zm \in \mathbb{Z}. Which equation follows?
Check yourself
To prove that a rational number aa plus an irrational number bb is irrational, assume a+ba + b is rational. Write a=pqa = \frac{p}{q} and a+b=rsa + b = \frac{r}{s}, with p,q,r,s∈Zp, q, r, s \in \mathbb{Z} and q,s≠0q, s \ne 0. Which expression is bb?

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 p1,p2,…,pnp_{1}, p_{2}, \ldots, p_{n}.

2. Let N=p1p2⋯pn+1N = p_{1}p_{2} \cdots p_{n} + 1. NN is greater than 11, so it has at least one prime factor.

3. Dividing NN by any pip_{i} on the list leaves remainder 11. So no prime on the list is a factor of NN.

4. So NN has a prime factor that is not on the list. This contradicts the list holding every prime. So there are infinitely many primes.

NN itself need not be prime. For example, 2×3×5×7×11×13+1=30031=59×5092 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30031 = 59 \times 509. Its prime factors, 5959 and 509509, are simply not on the list.

Check yourself
Let N=2×3×5×7×11+1N = 2 \times 3 \times 5 \times 7 \times 11 + 1. What is the remainder when NN is divided by 77?

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.

Worked exampleShow that the statement 'n2+n+17n^{2} + n + 17 is prime for every n∈Nn \in \mathbb{N}' is false.

Try it first, then reveal one step at a time.

  1. Try small values: n=0,1,2,3n = 0, 1, 2, 3 give 17,19,23,2917, 19, 23, 29, all prime. Testing one at a time is slow, so look for a value that builds in a factor.
Worked exampleConsider the statement 'ex>x3\mathrm{e}^{x} > x^{3} for all x>0x > 0'. Use your calculator to find a counterexample, and explain why it is one.

Try it first, then reveal one step at a time.

  1. Write down what you graph: y=exy = \mathrm{e}^{x} and y=x3y = x^{3} for 0<x≤50 < x \le 5. The calculator finds the intersections at x≈1.857x \approx 1.857 and x≈4.536x \approx 4.536.
Check yourself
Which value of nn is a counterexample to the statement 'n2−n+11n^{2} - n + 11 is prime for all n∈Z+n \in \mathbb{Z}^{+}'?
Check yourself
Which value of xx is a counterexample to the statement 'if x2>9x^{2} > 9, then x>3x > 3'?

Common mistakes

  • Writing 'let n=kn = k' as the assumption. Write 'Assume the result is true for n=kn = k', then the full statement with kk in place of nn.
  • Checking the basis on one side only. At n=1n = 1, work out the LHS and the RHS separately and show they are equal.
  • Getting the new term wrong. Substitute r=k+1r = k + 1 into the general term with care: for 1r(r+1)\frac{1}{r(r + 1)} it is 1(k+1)(k+2)\frac{1}{(k + 1)(k + 2)}.
  • A conclusion without its reasons. Say the result is true for n=1n = 1, and that true for n=kn = k implies true for n=k+1n = k + 1, so it is true for all n∈Z+n \in \mathbb{Z}^{+}.
  • 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

Learn this∑r=1k+1ur=∑r=1kur+uk+1\sum_{r=1}^{k+1} u_{r} = \sum_{r=1}^{k} u_{r} + u_{k+1}
Learn thisInduction has four parts: basis P(1)P(1), assumption P(k)P(k), inductive step from P(k)P(k) to P(k+1)P(k + 1), and conclusion. Write all four.
Learn thisAssume 'P(k)P(k) is true' in full. 'Let n=kn = k' is not an assumption.
Learn thisFor divisibility by dd, write the assumption as an equation with dmdm, m∈Zm \in \mathbb{Z}. Finish with d×(an integer)d \times (\text{an integer}) and say why the bracket is an integer.
Learn thisContradiction: assume the statement is false, deduce something impossible, then name the contradiction.
Learn this3\sqrt{3} is irrational: from pq\frac{p}{q} in lowest terms, pp and qq both turn out to be multiples of 33.
Learn thisOne counterexample disproves a 'for all' statement. Show the calculation and say why it fails.

Practise this

16 past-paper questions on 1.15 in the AA HL bank, each with a mark scheme and a worked explanation.

Practise 1.15 →