The structure of a proof by mathematical induction

1) Prove the base case. 2) Assume true for $n = k$. 3) Prove true for $n = k + 1$ using the assumption. 4) Write the conclusion sentence.

What is enough to disprove a statement 'for all $n$'?

A single counterexample. E.g. $n^2 + n + 11$ is prime for all $n$? False: $n = 10$ gives $121 = 11^2$.

AHL 1.15 Proof by induction, contradiction and counterexample — IB Mathematics: Analysis and Approaches notes and practice questions

Induction proves statements for every natural number, contradiction proves a claim by showing its opposite is impossible, and a single counterexample disproves a general claim. Study guide, 1 practice questions with markschemes and 2 flashcards. Free.

Steps of mathematical induction · Induction for series, divisibility and derivatives · Proof by contradiction (e.g. irrationality) · Disproof by counterexample · Writing a rigorous conclusion

Study guide

Why proof matters

Checking a statement for many examples does not prove it. The expression $n^2 + n + 41$ gives a prime for every $n$ from 0 to 39, yet at $n = 40$ it equals $1681 = 41^2$. HL Paper 1 and 2 expect three tools to settle such questions rigorously.

Proof by induction

Think of an infinite line of dominoes. To knock all of them down you need two facts: the first one falls, and each falling domino knocks over the next. Induction has the same structure.

Basis: show the statement $P(n)$ is true for the first value (often $n = 1$).
Assumption: assume $P(k)$ is true for some integer $k \ge 1$.
Inductive step: using that assumption, prove $P(k + 1)$.
Conclusion: since $P(1)$ is true, and $P(k)$ true implies $P(k + 1)$ true, $P(n)$ is true for all $n \in \mathbb{Z}^+$.

Worked example: a series

Prove that $\sum_{r=1}^{n} (2r - 1) = n^2$ for all positive integers $n$.

Basis: $n = 1$ gives LHS $= 1$, RHS $= 1^2 = 1$. True.
Assume $\sum_{r=1}^{k} (2r - 1) = k^2$.
Then $\sum_{r=1}^{k+1} (2r - 1) = k^2 + \big(2(k + 1) - 1\big) = k^2 + 2k + 1 = (k + 1)^2$, which is the statement for $n = k + 1$.
Conclusion as in step 4.

Divisibility. To show $5^n - 1$ is divisible by 4: the basis is $5 - 1 = 4$. Assume $5^k - 1 = 4m$ for an integer $m$. Then $5^{k+1} - 1 = 5 \cdot 5^k - 1 = 5(5^k - 1) + 4 = 20m + 4 = 4(5m + 1)$, a multiple of 4. The key move is to rewrite the $(k+1)$ case so the assumed expression appears inside it.

Derivatives. Induction can also prove formulas such as $\frac{d^n}{dx^n}(x e^x) = (x + n)e^x$: differentiate the assumed $k$th derivative once to get the $(k+1)$th.

Proof by contradiction

Assume the opposite of what you want, then reason until something impossible appears. The assumption must be false.

Classic example: $\sqrt{2}$ is irrational. Suppose $\sqrt{2} = \frac{p}{q}$ in lowest terms. Then $p^2 = 2q^2$, so $p^2$ is even and therefore $p$ is even, say $p = 2s$. Then $4s^2 = 2q^2$, so $q^2 = 2s^2$ and $q$ is even too. But then $\frac{p}{q}$ was not in lowest terms: contradiction. Hence $\sqrt{2}$ is irrational.

Disproof by counterexample

To show a statement "for all $x$..." is false, one specific case where it fails is enough. Claim: "$2^n + 1$ is prime for all positive integers $n$." Counterexample: $n = 3$ gives 9, which is not prime. State the counterexample clearly and show the calculation.

Common mistakes

Assuming $P(k + 1)$ and working backwards to something true.
Skipping the basis step or the written conclusion; both carry marks.
Writing "assume true for $n = k$" without saying $k$ is a positive integer.
In contradiction proofs, not saying which assumption has been contradicted.

Exam tips

Write the target $P(k + 1)$ explicitly before you start the step, so you know what you are aiming for.
Use the exact conclusion sentence structure; examiners look for all its parts.
For divisibility, introduce an integer ($5^k - 1 = 4m$) rather than words.

Cheat sheet

Induction template

Show $P(1)$ true.
Assume $P(k)$ true, $k \in \mathbb{Z}^+$.
Prove $P(k+1)$ using the assumption.
"Since $P(1)$ is true and $P(k) \Rightarrow P(k+1)$, $P(n)$ is true for all $n \in \mathbb{Z}^+$."

Useful moves

Series: $S_{k+1} = S_k + u_{k+1}$
Divisibility: write $f(k) = dm$, rewrite $f(k+1)$ as $(\ldots)f(k) + (\text{multiple of } d)$
Derivatives: differentiate the $k$th derivative once

Contradiction: assume $\neg P$, reach an impossibility, conclude $P$.
Counterexample: one explicit failing case disproves "for all".

Key definitions

Practice questions

HLPaper 1Challenging

Question 1

Use mathematical induction to prove that $7^n - 3^n$ is divisible by 4 for all $n \in \mathbb{Z}^+$.

(a) [7]

Prove the statement by mathematical induction.

Markscheme

1 Base case: $n = 1$ gives $7 - 3 = 4$, which is divisible by 4
1 Assumes true for $n = k$: $7^k - 3^k = 4m$ for some $m \in \mathbb{Z}$
1 Considers $n = k + 1$: $7^{k+1} - 3^{k+1}$
1 Splits correctly, e.g. $7 \cdot 7^k - 3 \cdot 3^k = 7(7^k - 3^k) + 4 \cdot 3^k$
1 Uses assumption: $= 28m + 4 \cdot 3^k = 4(7m + 3^k)$
1 States this is divisible by 4
1 Conclusion: true for $n = 1$, and true for $n = k$ implies true for $n = k + 1$, so true for all $n \in \mathbb{Z}^+$

AHL 1.15 Proof by induction, contradiction and counterexample