4.01a - Proof by induction | OCR A-Level Further Mathematics A

Prove statements about every integer in a specified range, using one starting case and a step that carries truth from one integer to the next. You will use induction for divisibility, matrix powers and inequalities involving exponentials and factorials, with particular care over where each proof starts.

Why induction proves infinitely many cases

Can you prove that $5^{2027} - 8109$ is divisible by $16$ , without calculating the huge power? The first few cases of $5^n - 1 - 4n$ are encouraging:

\begin{array}{c|rrrr} n & 0 & 1 & 2 & 3 \\ \hline 5^n - 1 - 4n & 0 & 0 & 16 & 112 \end{array}

Each is a multiple of $16$ . But checking even a million cases would leave the next one unproved. We need a way of reaching every case, however large its index.

Here is a warning with surprisingly good camouflage: $n^2 + n + 41$ is prime for every integer from $0$ to $39$ . At $n = 40$ , however, it equals $1681 = 41^2$ . Forty successes are evidence for a pattern, not a proof of it.

You already know

A statement about all integers needs an argument that covers all of them. A counterexample disproves such a statement; a collection of successful checks does not prove it. Laws of indices give $a^{k+1} = a \times a^k$ .

Write $P(n)$ for the statement you want to prove at the integer $n$ . Induction has two jobs: establish a starting point, then prove a rule that takes you from any allowed case to the next.

[DIAGRAM: asset_name: A starting case and a reusable implication; asset_slug: h245_4_01_induction_chain; caption: The base case starts the chain; the same proved implication carries truth from each integer to its successor; description: Four blue rounded boxes labelled P(1), P(2), P(3), P(4) and an ellipsis are joined by sage right arrows. The first box is marked base case. Above the arrows a bracket says the same implication P(k) implies P(k+1), for any integer k at least 1. Below, a separate statement says the starting case and the reusable step are both needed.]
The base case starts the chain

Proof by induction

A proof by mathematical induction establishes a statement $P(n)$ for every integer $n \ge n_0$ by proving the base case $P(n_0)$ , then showing that, for an arbitrary integer $k \ge n_0$ , the assumption $P(k)$ implies $P(k+1)$ . For example, a proof starting at $n_0 = 3$ reaches $3, 4, 5, \ldots$ . It does not establish the cases $1$ and $2$ .

You are allowed to assume one unspecified case while proving the implication. That is not assuming the final answer: you still have to show that this one case forces the next. The base case then starts the chain: $P(n_0)$ gives $P(n_0+1)$ , which gives $P(n_0+2)$ , and so on. Every integer in the range is reached after finitely many steps.

The induction principle

For an integer $n_0$ , if

P(n_0)\text{ is true}

and, for every integer $k \ge n_0$ ,

P(k) \Longrightarrow P(k+1)

then $P(n)$ is true for every integer $n \ge n_0$ .
Not in the formula booklet: learn it.

The conclusion must connect these two jobs. A useful full sentence is: “The result is true for $n = n_0$ , and truth for $n = k$ implies truth for $n = k+1$ ; therefore it is true for every integer $n \ge n_0$ , by induction.” Replace $n_0$ by the actual starting integer.

Key idea

The assumption is the input to an implication, not permission to assume every case. Prove the starting case and the reusable step separately.

The following attempted proof has a circular argument hidden inside otherwise familiar wording.

Divisibility and the inductive assumption

To prove divisibility, turn the assumed statement into a multiple of the required divisor, then make that multiple appear inside the next case.

Divisible by an integer

For integers $a$ and $d$ , with $d \ne 0$ , $a$ is divisible by $d$ if $a = dm$ for some integer $m$ . For example, $0 = 16 \times 0$ is divisible by $16$ . An expression $16m + 1$ with integer $m$ is not divisible by $16$ .

The integer condition matters. Writing an expression as $16$ times an unspecified real number says nothing about divisibility. In an induction proof, introduce an integer $m$ in the assumption and keep the final bracket integer-valued.

Worked example 1: a power minus one

Question. Prove by induction that $5^n - 1$ is divisible by $4$ for every integer $n \ge 0$ .

Plan. Start at $n = 0$ , assume $5^k - 1 = 4m$ , then separate off a multiple of this assumed expression.

5^0 - 1 = 0 = 4 \times 0 \qquad \text{base case is true}

Assume $5^k - 1 = 4m$ for some integer $m$ , where $k \ge 0$ is an arbitrary integer. Then

\begin{aligned} 5^{k+1} - 1 &= 5(5^k - 1) + 4 && \text{expose the assumption} \\ &= 5(4m) + 4 && \text{use the assumption} \\ &= 4(5m + 1) && \text{factor out } 4 \end{aligned}

Why this step? Multiplying the whole assumed expression by $5$ nearly produces the next case; the correction is another multiple of $4$ .

Answer. Since $5m + 1$ is an integer, truth for $n = k$ implies truth for $n = k+1$ . The result is true for $n = 0$ , so it is true for every integer $n \ge 0$ , by induction.

Check. At $n = 2$ , $5^2 - 1 = 24 = 4 \times 6$ .

Worked example 2 adds a linear correction, $-4n$ , to the expression. That correction makes a stronger divisibility statement possible; track it as carefully as the power.

Worked example 2: the corrected power

Question. Prove by induction that $5^n - 1 - 4n$ is divisible by $16$ for every integer $n \ge 0$ .

Plan. Assume the corrected expression equals $16m$ , then compare the next case with five times the assumed case.

5^0 - 1 - 4(0) = 0 = 16 \times 0 \qquad \text{base case is true}

Assume $5^k - 1 - 4k = 16m$ for an integer $m$ , where $k \ge 0$ . Then

\begin{aligned} 5^{k+1} - 1 - 4(k+1) &= 5(5^k - 1 - 4k) + 16k && \text{regroup the next case} \\ &= 5(16m) + 16k && \text{use the assumption} \\ &= 16(5m + k) && \text{an integer multiple of } 16 \end{aligned}

Why this step? The correction $16k$ is exactly the difference between the next expression and five times the previous expression. Expanding both sides checks the regrouping.

Answer. Truth for $n = k$ implies truth for $n = k+1$ . As the result is true for $n = 0$ , it is true for every integer $n \ge 0$ , by induction.

Check. At $n = 3$ , $125 - 1 - 12 = 112 = 16 \times 7$ . Expanding the regrouped line gives $5^{k+1} - 5 - 4k$ , equal to the required expression.

These divisibility results are not in the formula booklet: derive them when asked. The opening puzzle is now solved: $8109 = 1 + 4(2027)$ , so $5^{2027} - 8109$ is divisible by $16$ .

Watch out

Wrong: assume $5^k - 1 - 4k = 16k$ . The quotient need not equal the index. Right: write $5^k - 1 - 4k = 16m$ , where $m$ is an integer, then show the next expression is $16$ times an integer too.

A complete proof has a starting case, an actual use of the assumption and a conclusion about the entire stated range.

Exam tip

If OCR asks for all integers $n \ge 0$ , check $n = 0$ . Starting at $1$ leaves a case unproved. The conclusion must say that truth for $k$ implies truth for $k+1$ , and connect this to the base case.

The next question changes the power's base from $5$ to $9$ . Comparing the next expression with nine times the assumed expression produces the useful correction term.

Proving a matrix-power formula

A matrix-power formula predicts every entry after repeated multiplication, so induction tests the whole prediction with one further matrix multiplication.

You already know

$\mathbf{A}^n$ means $n$ repeated factors of a square matrix. Multiply rows by columns, and keep the order: $\mathbf{A}^{k+1} = \mathbf{A}^k\mathbf{A}$ . A matrix power is not obtained by raising each entry to that power.

For $\mathbf{A} = \begin{pmatrix}1&1\\0&1\end{pmatrix}$ , direct multiplication gives $\mathbf{A}^2 = \begin{pmatrix}1&2\\0&1\end{pmatrix}$ and $\mathbf{A}^3 = \begin{pmatrix}1&3\\0&1\end{pmatrix}$ . The top-right entry appears to increase by $1$ each time. Induction proves that it always does.

Worked example 3: an entry growing linearly

Question. Prove that, for every positive integer $n$ ,

\begin{pmatrix}1&1\\0&1\end{pmatrix}^{n} = \begin{pmatrix}1&n\\0&1\end{pmatrix}

Plan. Verify $n = 1$ , assume the full matrix formula for $n = k$ , then multiply on the right by one more copy of the matrix.

\begin{pmatrix}1&1\\0&1\end{pmatrix} = \mathbf{A} \qquad \text{base case is true}

Assume $\mathbf{A}^k = \begin{pmatrix}1&k\\0&1\end{pmatrix}$ , where $k \ge 1$ . Then

\begin{aligned} \mathbf{A}^{k+1} &= \mathbf{A}^k\mathbf{A} && \text{one more factor} \\ &= \begin{pmatrix}1&k\\0&1\end{pmatrix}\begin{pmatrix}1&1\\0&1\end{pmatrix} && \text{use the assumption} \\ &= \begin{pmatrix}1&1+k\\0&1\end{pmatrix} && \text{rows by columns} \\ &= \begin{pmatrix}1&k+1\\0&1\end{pmatrix} && \text{the required next form} \end{aligned}

Why this step? Multiplying by the original matrix adds exactly $1$ to the changing entry while keeping the other three entries fixed.

Answer. Truth for $n = k$ implies truth for $n = k+1$ . The result is true for $n = 1$ , so it is true for all positive integers $n$ , by induction.

Check. At $n = 2$ , row-by-column multiplication gives top-right entry $1(1) + 1(1) = 2$ , as predicted.

Worked example 4 changes only the common scale of the matrix: every entry is doubled. Each multiplication brings in another factor of $2$ , as well as changing the top-right entry.

Worked example 4: a scale factor in every power

Question. Prove that, for $\mathbf{B} = \begin{pmatrix}2&2\\0&2\end{pmatrix}$ and every positive integer $n$ ,

\mathbf{B}^n = 2^n\begin{pmatrix}1&n\\0&1\end{pmatrix}

Plan. Check the factor $2^n$ at $n = 1$ , then retain it outside the matrix during the inductive multiplication.

2^1\begin{pmatrix}1&1\\0&1\end{pmatrix} = \begin{pmatrix}2&2\\0&2\end{pmatrix} \qquad \text{base case is true}

Assume $\mathbf{B}^k = 2^k\begin{pmatrix}1&k\\0&1\end{pmatrix}$ , where $k \ge 1$ . Then

\begin{aligned} \mathbf{B}^{k+1} &= \mathbf{B}^k\mathbf{B} && \text{one more factor} \\ &= 2^k\begin{pmatrix}1&k\\0&1\end{pmatrix}\begin{pmatrix}2&2\\0&2\end{pmatrix} && \text{use the assumption} \\ &= 2^k\begin{pmatrix}2&2+2k\\0&2\end{pmatrix} && \text{multiply the matrices} \\ &= 2^{k+1}\begin{pmatrix}1&k+1\\0&1\end{pmatrix} && \text{take out the new factor } 2 \end{aligned}

Why this step? Leaving $2^k$ outside avoids unnecessary expansion. The next multiplication supplies the additional factor needed for $2^{k+1}$ .

Answer. Truth for $n = k$ implies truth for $n = k+1$ . The result is true for $n = 1$ , so it is true for all positive integers $n$ , by induction.

Check. $\mathbf{B}^2 = \begin{pmatrix}4&8\\0&4\end{pmatrix} = 4\begin{pmatrix}1&2\\0&1\end{pmatrix}$ , as predicted.

Neither matrix-power result is in the formula booklet: derive it when asked. A formula may be supplied in the question precisely because the task is to prove it.

Watch out

Wrong: $\begin{pmatrix}1&1\\0&1\end{pmatrix}^2 = \begin{pmatrix}1&1\\0&1\end{pmatrix}$ , obtained by squaring each entry. Right: row-by-column multiplication gives $\begin{pmatrix}1&2\\0&1\end{pmatrix}$ . Raising a matrix to a power means multiplying matrices, not entries.

Writing the intended $k+1$ form in advance is useful as a target. Obtain it from the assumed formula, rather than assuming that target as another equality.

Induction with strict inequalities

An inequality proof needs a chain of justified comparisons that reaches the next target; replacing an inequality by an equality throws away the assumption's meaning.

For example, $2^3 = 8 > 6 = 2(3)$ . Doubling the left side at the next step gives $2^4 = 16$ , whereas the target $2n$ only increases to $8$ . Induction captures this difference in growth without checking each integer.

You already know

Multiplying an inequality by a positive number preserves its direction; multiplying by a negative number reverses it. A chain $a > b \ge c$ proves $a > c$ . The equality case in one link does not remove a strict inequality in another link.

For each proof, write the next target first in your rough work. You then know what the bound supplied by the assumption still has to beat.

Worked example 5: an exponential beats a linear expression

Question. Prove by induction that $2^n > 2n$ for all integers $n \ge 3$ .

Plan. Check $n = 3$ , double the assumed inequality and compare $4k$ with $2(k+1)$ .

2^3 = 8 > 6 = 2(3) \qquad \text{base case is true}

Assume $2^k > 2k$ for an arbitrary integer $k \ge 3$ . Then

\begin{aligned} 2^{k+1} &= 2 \times 2^k && \text{separate one factor} \\ &> 4k && \text{multiply the assumption by } 2 \\ &\ge 2k + 2 = 2(k+1) && 2k \ge 2 \text{ for } k \ge 3 \end{aligned}

Why this step? The assumption gives $4k$ , not the required $2(k+1)$ . The final comparison is the bridge between them.

Answer. Truth for $n = k$ implies truth for $n = k+1$ . Since the inequality is true for $n = 3$ , it is true for every integer $n \ge 3$ , by induction.

Check. At $n = 4$ , $16 > 8$ . The start cannot be $n = 2$ , because $2^2 = 2(2)$ , not a strict inequality.

Worked example 6 changes the coefficient of $n$ from $2$ to $3$ . Check the starting integer again: the old base case no longer works.

Worked example 6: the same method with a later start

Question. Prove by induction that $2^n > 3n$ for all integers $n \ge 4$ .

Plan. Start at $4$ , double the assumed bound and show that it exceeds the next linear target.

2^4 = 16 > 12 = 3(4) \qquad \text{base case is true}

Assume $2^k > 3k$ for an integer $k \ge 4$ . Then

\begin{aligned} 2^{k+1} &= 2 \times 2^k && \text{separate one factor} \\ &> 6k && \text{use the assumption} \\ &\ge 3k + 3 = 3(k+1) && 3k \ge 3 \text{ for } k \ge 4 \end{aligned}

Why this step? Once $6k \ge 3(k+1)$ is proved, the strict inequality from the assumption makes the final result strict too.

Answer. Truth for $n = k$ implies truth for $n = k+1$ . The inequality is true for $n = 4$ , so it is true for all integers $n \ge 4$ , by induction.

Check. At $n = 3$ , $8 < 9$ , explaining the later start. At $n = 5$ , $32 > 15$ .

These particular bounds are not in the formula booklet: derive them when asked. The transferable method is to keep the assumed inequality and explicitly justify the comparison with the next target.

Watch out

Wrong: “Assume $2^k = 3k$ , so $2^{k+1} = 6k$ .” The statement being proved is an inequality. Right: assume $2^k > 3k$ , giving $2^{k+1} > 6k$ , then compare $6k$ with $3(k+1)$ .

The next question changes the coefficient once more. Its stated domain already supplies a valid base case.

Factorials and changing bases

For a factorial, the next case is obtained by multiplying by $k+1$ , so the new factor must appear explicitly in your inductive step.

Factorial

For a positive integer $n$ , $n! = 1 \times 2 \times \cdots \times n$ ; also $0! = 1$ . In particular, $(k+1)! = (k+1)k!$ . For example, $4! = 24$ ; it is not $4^4$ .

Compare $4! = 24$ with $2^{4-1} = 8$ and $4^4 = 256$ . A factorial can sit above one exponential expression and below another. The second comparison has a base that changes with the index, so no claim about fixed-base exponential growth is being made.

Worked example 7: a lower bound for a factorial

Question. Prove by induction that $n! \ge 2^{n-1}$ for all positive integers $n$ .

Plan. Start at $1$ , then use $(k+1)! = (k+1)k!$ and $k+1 \ge 2$ .

1! = 1 = 2^0 \qquad \text{base case is true}

Assume $k! \ge 2^{k-1}$ for an integer $k \ge 1$ . Then

\begin{aligned} (k+1)! &= (k+1)k! && \text{separate the final factor} \\ &\ge (k+1)2^{k-1} && k+1 > 0 \\ &\ge 2 \times 2^{k-1} = 2^k && k+1 \ge 2 \end{aligned}

Why this step? The factorial gains a factor of at least $2$ , exactly what is needed to move the exponential bound from $2^{k-1}$ to $2^k$ .

Answer. Truth for $n = k$ implies truth for $n = k+1$ . The result is true for $n = 1$ , so it holds for all positive integers $n$ , by induction.

Check. At $n = 2$ , both sides equal $2$ ; at $n = 3$ , $6 > 4$ . The non-strict sign is necessary at the first two integers.

Worked example 8 changes the comparison to the changing-base power $n^n$ . The next target is $(k+1)^{k+1}$ , not $k^{k+1}$ , and both the base and exponent must advance.

Worked example 8: an upper bound for a factorial

Question. Prove by induction that $n! < n^n$ for all integers $n \ge 2$ .

Plan. Start at $2$ , multiply the assumption by $k+1$ , then increase the base of the remaining power from $k$ to $k+1$ .

2! = 2 < 4 = 2^2 \qquad \text{base case is true}

Assume $k! < k^k$ for an integer $k \ge 2$ . Then

\begin{aligned} (k+1)! &= (k+1)k! && \text{separate the final factor} \\ &< (k+1)k^k && \text{multiply by positive } k+1 \\ &< (k+1)(k+1)^k && 0 < k < k+1 \\ &= (k+1)^{k+1} && \text{combine equal bases} \end{aligned}

Why this step? Multiplication gives $(k+1)k^k$ . Replacing the smaller positive base $k$ by $k+1$ then reaches the exact next target.

Answer. Truth for $n = k$ implies truth for $n = k+1$ . The inequality is true for $n = 2$ , so it is true for every integer $n \ge 2$ , by induction.

Check. At $n = 3$ , $6 < 27$ . At $n = 1$ , $1! = 1^1$ , so the strict inequality cannot include that case.

The factorial identity and both bounds in this part are not in the formula booklet: learn the identity and derive the bounds when asked. Neither needs a formula for the exact size of $n!$ .

Watch out

Wrong: $(k+1)! = k! + 1$ , or $(k+1)^{k+1} = k^k + 1$ . Increasing an index does not mean adding one to the value. Right: write the complete next expression first, then use the operation that actually connects the cases.

The huge power from the opening question needed no huge calculation: its divisibility follows from the same base-and-step logic used for matrices and factorials. A proof can be short even when its examples are enormous.

Quick Recap

Check the first integer in the stated domain, assume one arbitrary case, and use it to prove the next case.
For divisibility, write the assumption as an integer multiple of the divisor and expose it inside the next expression.
For matrix powers, multiply the assumed whole matrix by one more copy of the original matrix.
For inequalities, preserve the correct sign and justify the comparison between your bound and the next target.
Factorials advance by $(k+1)! = (k+1)k!$ ; a changing-base power requires both its base and exponent to advance.

The opening number is $5^{2027} - 1 - 4(2027)$ , so the proved divisibility result makes it a multiple of $16$ without calculating the power.

Last Accessed

Pure Core

Statistics

Mechanics

Discrete Mathematics

Additional Pure Mathematics

4.01a - Proof by induction

Why induction proves infinitely many cases

Divisibility and the inductive assumption

Proving a matrix-power formula

Induction with strict inequalities

Factorials and changing bases

Quick Recap

Learn faster with Nova