1.15 Proof by induction, contradiction and counterexampleIB Maths: Analysis and Approaches HL: Revision notes

Mathematical induction proves a statement $P(n)$ for every $n \in \mathbb{Z}^{+}$ (or every integer from some starting value).

1. Basis: show $P(1)$ is true.
2. Assumption: assume $P(k)$ is true for some $k \in \mathbb{Z}^{+}$.
3. Inductive step: using the assumption, show $P(k+1)$ is true.
4. Conclusion: '$P(1)$ is true, and $P(k)$ true implies $P(k+1)$ true, so $P(n)$ is true for all $n \in \mathbb{Z}^{+}$ by mathematical induction.'

IB markschemes award the final R mark only if the basis and inductive step are both done properly, so always write the full conclusion.

• Sums: add the $(k+1)$th term to the assumed sum, then factorise: $\frac{k(k+1)(k+2)}{3} + (k+1)(k+2) = \frac{(k+1)(k+2)(k+3)}{3}$.
• Divisibility: to show $5^{n} - 1$ is divisible by 4, assume $5^{k} - 1 = 4m$, then $5^{k+1} - 1 = 5(5^{k}) - 1 = 5(4m + 1) - 1 = 20m + 4 = 4(5m + 1)$.
• Differentiation: differentiate the assumed $n$th derivative, e.g. $f^{(k)}(x) = 2^{k-1}(2x + k)e^{2x}$ gives $f^{(k+1)}(x) = 2^{k}(2x + k + 1)e^{2x}$.
• Complex numbers: De Moivre's theorem — multiply $\operatorname{cis}(k\theta)$ by $\operatorname{cis}\theta$ and use compound angle identities.

In a proof by contradiction you assume the statement is false and show this leads to something impossible.

Irrationality of $\sqrt[3]{5}$: assume $\sqrt[3]{5} = \frac{p}{q}$ in lowest terms. Then $p^{3} = 5q^{3}$, so 5 divides $p$ (5 is prime); write $p = 5m$, giving $q^{3} = 25m^{3}$, so 5 divides $q$ — contradicting lowest terms. The same method proves $\sqrt{3}$ irrational.

Rational + irrational is irrational: if $a + b = \frac{m}{n}$ with $a = \frac{p}{q}$ rational, then $b = \frac{mq - np}{nq}$ would be rational — contradiction.

Euclid: infinitely many primes: assume there are finitely many, $p_1, p_2, \ldots, p_n$. Then $N = p_1p_2\cdots p_n + 1$ leaves remainder 1 when divided by every $p_i$, so its prime factors are not in the list — contradiction.

A universal claim ('for all $n$…') is shown false by one counterexample. For $n^{2} + 41n + 41$: when $n = 41$, $41^{2} + 41^{2} + 41 = 41(83)$, which is not prime.

Stating the counterexample alone is not enough: you must show why it breaks the claim, e.g. by exhibiting the factorisation, or evaluating both sides of an inequality.

No number of examples that work ever proves a universal claim: $n^{2} + n + 41$ is prime for $n = 1, 2, \ldots, 39$, yet fails at $n = 40$.