IB Analysis and Approaches HL · Algebra review and mathematical induction · Section 5 of 6

Proof and mathematical induction

3 worked examples · By Álvaro López

Key idea

To prove something is to justify, with logical steps, that a statement is true for all cases, not only for those you have tested. In Paper 1 of HL there is almost always a proof by induction, and it is marked by its structure: base case, hypothesis, inductive step and a concluding sentence.

What proving means (and what it does not)

Checking a formula for $n = 1, 2, 3$ does not prove it: it only makes the conjecture believable. A proof is a chain of deductions, each one justified, that starts from what is known (definitions, properties already proved) and reaches what is to be shown, relying on the fact that it holds for any permitted value of the variables.

Two tools used in every proof with integers:

An even integer is written $2 m$ and an odd one $2 m + 1$ , with $m \in Z$ .
A multiple of $3$ is written $3 m$ ; the others, $3 m + 1$ or $3 m + 2$ . In general, a multiple of $d$ is $d \cdot m$ with $m \in Z$ .

To finish, the IB accepts closing with the sentence "proof complete" or with the symbol $■$ (or "Q.E.D."). What matters is that the conclusion is stated.

Direct proof

You start from the hypothesis and advance to the conclusion. In algebraic identities you work on one side until you obtain exactly the other (or on both sides until they reach the same expression); you do not "move terms" from one side to the other, because that amounts to assuming the equality you are trying to prove.

Proof by counterexample

To disprove a general statement ("for all $n$ …") it is enough to find a single case in which it fails. A counterexample does not prove that something is true, only that it is false.

The expression $n^{2} + n + 41$ gives a prime number for $n = 0, 1, 2, \dots, 39$ (40 consecutive values), and yet the claim "it is prime for every integer $n \geq 0$ " is false: for $n = 40$ , $4 0^{2} + 40 + 41 = 1681 = 4 1^{2},$ which is not prime. This case shows why 40 checks prove nothing.

Proof by contradiction

Assume the statement is false, deduce an absurd consequence (something that contradicts a given fact, a hypothesis or a known result), and conclude that the assumption was impossible, so the statement is true.

Mathematical induction

The idea

Induction is for statements $P (n)$ that depend on an integer $n \in Z^{+}$ (a formula for a sum, a divisibility, an inequality). It works like a row of dominoes: if the first one falls, and each domino that falls knocks over the next, they all fall. Here "the first falls" is $P (1)$ , and "each domino knocks over the next" is $P (k) \Rightarrow P (k + 1)$ for any $k$ . With $P (1)$ and the implication you get $P (2)$ , from $P (2)$ you get $P (3)$ , and so on without end.

Both parts are essential: without the base case the chain never starts (a statement can satisfy $P (k) \Rightarrow P (k + 1)$ and still be false), and without the inductive step you have only checked one case.

Structure expected in the exam

The conclusion is not decoration: in IB marking schemes one mark is reserved for it. The sentence must state both the base case and the implication $P (k) \Rightarrow P (k + 1)$ , and that mark is normally only awarded if you have already obtained the marks for the base case and the inductive step. With just "QED", or nothing, the mark is lost.

How to do the inductive step by type

Type of statement	What to do in $P (k + 1)$
Sum $\sum_{r = 1}^{n}$	The sum up to $k + 1$ is the sum up to $k$ plus the last term. Substitute the sum up to $k$ by the assumed formula and simplify to the formula with $k + 1$ .
Divisibility (" $f (n)$ is a multiple of $d$ ")	Write the hypothesis as $f (k) = d m$ with $m \in Z$ . Decompose $f (k + 1)$ so that $f (k)$ , or a multiple of it, appears, plus something clearly a multiple of $d$ .
Inequality	Start from the complicated side of $P (k + 1)$ , apply the hypothesis to bound it, and chain another inequality that you know how to prove. Justify what is used (for example, for which values of $k$ it holds).

Worked examples

Example 1 Basic

Conjecture a formula and prove it

Let $S_{n} = \frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \frac{1}{3 \cdot 4} + \dots + \frac{1}{n ( n + 1 )}$ .

a) Calculate $S_{1}$ , $S_{2}$ and $S_{3}$ as fractions.

b) Conjecture a formula for $S_{n}$ in terms of $n$ .

c) Prove by mathematical induction that your formula is true for all $n \in Z^{+}$ .

Solution

a) $S_{1} = \frac{1}{2}$ . $S_{2} = \frac{1}{2} + \frac{1}{6} = \frac{2}{3}$ . $S_{3} = \frac{2}{3} + \frac{1}{12} = \frac{8 + 1}{12} = \frac{3}{4}$ .

b) The results $\frac{1}{2}, \frac{2}{3}, \frac{3}{4}$ follow the pattern "the numerator is $n$ and the denominator is $n + 1$ ": $S_{n} = \frac{n}{n + 1} .$

c) Let $P (n)$ : $r = 1 \sum n \frac{1}{r ( r + 1 )} = \frac{n}{n + 1}$ .

Base case. For $n = 1$ : left side $\frac{1}{1 \cdot 2} = \frac{1}{2}$ ; right side $\frac{1}{1 + 1} = \frac{1}{2}$ . They coincide: $P (1)$ is true.
Hypothesis. Assume that $P (k)$ is true for some $k \in Z^{+}$ , that is, $\frac{1}{1 \cdot 2} + \dots + \frac{1}{k ( k + 1 )} = \frac{k}{k + 1} .$
Inductive step. We must prove $P (k + 1)$ : the sum up to $k + 1$ equals $\frac{k + 1}{k + 2}$ . The sum up to $k + 1$ is the sum up to $k$ plus the new term; we use the hypothesis: $\frac{1}{1 \cdot 2} + \dots + \frac{1}{k ( k + 1 )} + \frac{1}{( k + 1 ) ( k + 2 )} = \frac{k}{k + 1} + \frac{1}{( k + 1 ) ( k + 2 )} = \frac{k ( k + 2 ) + 1}{( k + 1 ) ( k + 2 )} = \frac{( k + 1 ) ^{2}}{( k + 1 ) ( k + 2 )} = \frac{k + 1}{k + 2} .$ This is exactly the right-hand side of $P (k + 1)$ .
Conclusion. Since $P (1)$ is true and $P (k)$ true implies $P (k + 1)$ true, by mathematical induction $P (n)$ is true for all $n \in Z^{+}$ . $■$

Note that the numerator $k^{2} + 2 k + 1$ is recognised as $(k + 1)^{2}$ because we already knew where we wanted to get: writing the target $\frac{k + 1}{k + 2}$ alongside helps guide the simplification.

Example 2 MediumProof

A divisibility by induction

Prove by mathematical induction that $8^{n} - 3^{n}$ is divisible by $5$ for all $n \in Z^{+}$ .

Solution

Let $P (n)$ : " $8^{n} - 3^{n}$ is a multiple of $5$ ".

Base case. For $n = 1$ : $8 - 3 = 5$ , which is a multiple of $5$ . $P (1)$ is true.
Hypothesis. Assume that $P (k)$ is true for some $k \in Z^{+}$ : $8^{k} - 3^{k} = 5 m$ with $m \in Z$ . Hence $8^{k} = 5 m + 3^{k}$ .
Inductive step. We must prove that $8^{k + 1} - 3^{k + 1}$ is a multiple of $5$ . We write $8^{k + 1} = 8 \cdot 8^{k}$ and use the hypothesis to substitute $8^{k}$ : $8^{k + 1} - 3^{k + 1} = 8 (5 m + 3^{k}) - 3 \cdot 3^{k} = 40 m + 8 \cdot 3^{k} - 3 \cdot 3^{k} = 40 m + 5 \cdot 3^{k} = 5 (8 m + 3^{k}) .$ As $8 m + 3^{k}$ is an integer, $8^{k + 1} - 3^{k + 1}$ is a multiple of $5$ : $P (k + 1)$ is true.
Conclusion. Since $P (1)$ is true and $P (k)$ true implies $P (k + 1)$ true, by mathematical induction $8^{n} - 3^{n}$ is divisible by $5$ for all $n \in Z^{+}$ . $■$

The idea of step 3 is always the same: make the hypothesis appear, and make what is left over a clear multiple of $5$ (here, $5 \cdot 3^{k}$ ).

Example 3 HardProof

An inequality starting at n = 5

Prove by mathematical induction that $2^{n} > n^{2}$ for every integer $n \geq 5$ .

Solution

Before proving it, it is worth seeing why $n \geq 5$ is asked: for $n = 2$ there is equality ( $4 = 4$ ), for $n = 3$ it is false ( $8 < 9$ ), and for $n = 4$ there is equality again ( $16 = 16$ ). It is true from $n = 5$ on ( $32 > 25$ ), and that is the base case. So the base case is not $n = 1$ .

Let $P (n)$ : $2^{n} > n^{2}$ .

Base case. For $n = 5$ : $2^{5} = 32$ and $5^{2} = 25$ , and $32 > 25$ . $P (5)$ is true.
Hypothesis. Assume that $P (k)$ is true for some integer $k \geq 5$ : $2^{k} > k^{2}$ .
Inductive step. We must prove that $2^{k + 1} > (k + 1)^{2}$ . We start from the power of $2$ and use the hypothesis: $2^{k + 1} = 2 \cdot 2^{k} > 2 k^{2} .$ Now we need to compare $2 k^{2}$ with $(k + 1)^{2}$ : $2 k^{2} - (k + 1)^{2} = k^{2} - 2 k - 1 = (k - 1)^{2} - 2.$ As $k \geq 5$ , $(k - 1)^{2} \geq 16 > 2$ , so $2 k^{2} - (k + 1)^{2} > 0$ , that is, $2 k^{2} > (k + 1)^{2}$ . Chaining, $2^{k + 1} > 2 k^{2} > (k + 1)^{2} .$ Hence $P (k + 1)$ is true.
Conclusion. Since $P (5)$ is true and $P (k)$ true implies $P (k + 1)$ true for all $k \geq 5$ , by mathematical induction $2^{n} > n^{2}$ for every integer $n \geq 5$ . $■$

In the exam: in inequalities, the two things that cost the most marks are writing a wrong base case (using $n = 1$ when it does not hold) and not justifying the second inequality in the chain. Always say for which values of $k$ the result you use is true (here, $k \geq 5$ ), and in the conclusion mention the real starting value.

Common mistakes

Summary

To prove is to deduce, with justified steps, for all values; checking cases is not proving, and a single counterexample does disprove a general statement.
Direct: from the hypothesis to the conclusion, working on one side (without "moving terms"). Integers: even $2 m$ , odd $2 m + 1$ , multiple of $d$ : $d m$ .
Contradiction: suppose the opposite, reach a concrete absurdity and conclude (classic example: $2$ is irrational).
Induction: base case, hypothesis $P (k)$ , inductive step $P (k) \Rightarrow P (k + 1)$ using the hypothesis, and a concluding sentence that mentions both parts.
Sums: sum up to $k + 1$ = sum up to $k$ + new term. Divisibility: write $f (k) = d m$ and make a multiple of $d$ appear. Inequalities: bound using the hypothesis and justify for which $k$ each step holds; the base case may not be $n = 1$ .
In the exam the structure earns the marks: do not omit the hypothesis or the conclusion.

Keep studying

Maths classes in Aldaia and online

Want to work on it together?

Free first consultation: we look at your level and your exam, and build a plan. Álvaro replies on WhatsApp.

Message us on WhatsApp