Proof by Mathematical Induction

Proof by mathematical induction is almost always one 3-mark question in Section II, and NESA's sample paper for the 2024 syllabus followed that pattern. The marks are predictable, so this is a focus area where good setting-out earns full marks.

• The nature of induction: the statement to be proved, the base case and the inductive step, and why together they prove the result for every integer in range.
• Sums: prove formulas for the sum of a series.
• Divisibility: prove that an expression is divisible by a given integer.
• False proofs: identify the error when only one of the two steps is actually true.

In Extension 1 the induction questions are about sums and divisibility. Induction proofs of inequalities and of results about sequences or geometry belong to Extension 2, so you do not need to study them for this course.

A proof by mathematical induction proves that a statement $S(n)$ is true for every integer $n\ge n_0$ (usually $n_0=1$). It has two steps.

1. Base case: show $S(n_0)$ is true by direct calculation.
2. Inductive step: assume $S(k)$ is true for some integer $k\ge n_0$, and use that assumption to show $S(k+1)$ is true.

The assumption in step 2 is called the inductive hypothesis. You are not assuming the result is true for every $k$, only for one particular $k$, and then showing truth passes on to the next integer.

Think of a row of dominoes. The base case knocks over the first domino. The inductive step shows every domino knocks over the next one. Together, all of them fall. Either step on its own proves nothing.

Setting out that earns the marks

1. Write the statement $S(n)$ and the values of $n$ it covers.
2. Base case: calculate the left side and the right side separately and show they are equal (or that the expression is divisible).
3. Write "Assume $S(k)$ is true for some integer $k\ge 1$" and write out exactly what that means.
4. Write what you need to prove for $n=k+1$, with the $k+1$ substituted in.
5. Do the algebra, showing where you use the assumption.
6. Conclude: "Hence $S(k+1)$ is true whenever $S(k)$ is true. Since $S(1)$ is true, by mathematical induction $S(n)$ is true for all integers $n\ge 1$."

For a sum, the key move in the inductive step is to split the sum to $k+1$ terms into the sum to $k$ terms plus the $(k+1)$th term. The sum to $k$ terms is then replaced using the assumption. Work out the $(k+1)$th term carefully by substituting $k+1$ into the general term.

Worked example 1: a sum of products

Prove by induction that for all integers $n\ge 1$

Base case $n=1$: LHS $=1\times 2=2$ and RHS $=\frac{1\times 2\times 3}{3}=2$. True.

Assume true for $n=k$, for some integer $k\ge 1$:

Prove true for $n=k+1$, that is, the sum to $k+1$ terms equals $\frac{(k+1)(k+2)(k+3)}{3}$. The new term is $(k+1)(k+2)$.

The middle step takes out the common factor $\frac{(k+1)(k+2)}{3}$, which leaves $k+3$. Factorising like this is much quicker than expanding everything.

Hence if the result is true for $n=k$ it is true for $n=k+1$. Since it is true for $n=1$, by mathematical induction it is true for all integers $n\ge 1$.

To say an expression is divisible by $d$ means it equals $d$ times an integer. So the assumption is written as an equation, for example $3^{2k}+7=8M$ where $M$ is an integer. Rearrange it to make the power the subject, substitute into the $k+1$ expression and factor out $d$.

Worked example 2: a divisibility proof

Prove by induction that $3^{2n}+7$ is divisible by 8 for all integers $n\ge 1$.

Base case $n=1$: $3^2+7=16=8\times 2$, which is divisible by 8.

Assume true for $n=k$: $3^{2k}+7=8M$ for some integer $M$, so $3^{2k}=8M-7$.

Prove true for $n=k+1$: show $3^{2k+2}+7$ is divisible by 8.

Since $9M-7$ is an integer, $3^{2k+2}+7$ is divisible by 8. Hence the result is true for $n=k+1$ whenever it is true for $n=k$, and since it is true for $n=1$, by mathematical induction it is true for all integers $n\ge 1$.

Note that $3^{2(k+1)}=3^{2k}\times 3^2$, not $3^{2k}\times 3$. Write the index law step out in full.

A false "proof by induction" usually has a step that looks right but is not. Check each step on its own:

• Base case missing or false. The inductive step can be perfectly valid for a statement that is never true.
• Inductive step fails. The base case works but the algebra does not actually show the $k+1$ case, often because the final expression is not really a multiple of $d$.
• Assuming what you want to prove. Starting from $S(k+1)$ and working backwards to something true is not a valid proof.

Worked example 3: a valid step, a false claim

A student claims $n^2+n+1$ is even for all integers $n\ge 1$. Their inductive step: assume $k^2+k+1=2M$. Then

which is even. Find the error.

The inductive step is correct algebra. The error is that the base case is false: when $n=1$, $1+1+1=3$, which is odd. In fact $n^2+n=n(n+1)$ is always even (a product of consecutive integers), so $n^2+n+1$ is always odd. The step "if true for $k$ then true for $k+1$" is true, but there is no first domino.

• Skipping the base case, or writing only "true for $n=1$" without showing the calculation.
• Writing the $(k+1)$th term wrongly, for example $k(k+1)+1$ instead of $(k+1)(k+2)$.
• Not using the assumption at all. If the inductive hypothesis never appears in your working, it is not an induction proof.
• Writing "assume true for all $k$". You assume it for one integer $k$.
• In divisibility proofs, not stating that the bracket (such as $9M-7$) is an integer.
• Expanding everything in a sum proof instead of taking out a common factor, then getting lost in the algebra.
• Leaving out the concluding statement.

• Expect about 3 marks: typically 1 for the base case, 1 for correctly stating and using the assumption, and 1 for completing the inductive step with a conclusion.
• Write what you are trying to prove for $n=k+1$ before you start the algebra. It tells you what form to aim for, and markers can see your target.
• For a sum, always write LHS as "sum to $k$ terms $+$ $(k+1)$th term", then substitute the assumption.
• For divisibility, $M$ must be stated to be an integer, and your final line must show $d\times$ (an integer).
• For a "find the error" question, say exactly which step fails and give a counterexample (a value of $n$ for which the statement is false) if there is one.
• Use the words "Assume", "Prove" and "Hence" as signposts. Clear structure is part of the marks.

• Advanced, Sequences and Series (MA12-SS): arithmetic and geometric series give formulas you can prove by induction, and sigma notation is used for the sums.
• Polynomials (ME11-PO): factorising expressions like $\frac{k(k+1)(k+2)}{3}+(k+1)(k+2)$ uses the same factor-taking skills.
• The binomial theorem (ME11-BT): an alternative way to prove some divisibility results, for example by writing $9^n=(8+1{)}^n$ and expanding.