Pp4 - Induction for sequences, series and matrices | OCR A-Level Further Mathematics B (MEI)

One calculation checks one case; a proof by induction reaches infinitely many. You will prove given formulae for sequence terms, finite sums and matrix powers, using the same logical structure each time. The skill is to make the next case follow from the previous one, with no gap hidden behind a pattern.

Why one step reaches every integer

Can a short proof justify the enormous sum $1^2 + 2^2 + \cdots + 1000000^2 = 333333833333500000$ , without adding a million terms?

For smaller sums, $1^2 = 1$ , $1^2 + 2^2 = 5$ and $1^2 + 2^2 + 3^2 = 14$ . These agree with the proposed formula $\dfrac{n(n+1)(2n+1)}{6}$ . Three checks are encouraging, but they leave every later integer unchecked. Induction supplies a different kind of argument: establish a first case, then prove that any true case forces the next case to be true.

Proof by induction

A proof by induction establishes a statement for every integer in a stated range by checking its first integer and proving that, for an arbitrary integer $k$ in the range, truth at $k$ implies truth at $k+1$ . The temporary assumption that the statement holds at $k$ is the induction hypothesis.

The hypothesis is conditional. You are not assuming that the formula is true for every integer; you are showing what would follow if it were true at one arbitrary integer. The base case starts this chain, so the implication can be used repeatedly.

[DIAGRAM: asset_name: The induction chain; asset_slug: induction_chain; caption: A verified first case and a universal next-step implication reach every positive integer; description: A row of four labelled boxes P(1), P(2), P(3), P(4), followed by an ellipsis. The first box is marked Check directly. Arrows between successive boxes are labelled Same proved implication. Beneath the row a separate general arrow P(k) to P(k+1) is labelled Prove this for an arbitrary integer k at least 1. A final note says Checking several boxes alone does not prove the arrows.]
A verified first case and a universal next-step implication reach every positive integer

For the square-sum problem, the first case is $n=1$ , and the next sum is the old sum plus $(k+1)^2$ . That gives the route for the proof in Part 3. Other problems connect neighbouring cases by a recurrence or by matrix multiplication.

Induction principle

Let $P(n)$ be a statement defined for integers $n\ge n_0$ , where $n_0$ is a fixed integer. If

\begin{aligned} P(n_0)&\text{ is true} && \text{base case} \\ P(k)\text{ true}&\implies P(k+1)\text{ true for every integer }k\ge n_0 && \text{inductive step} \end{aligned}

then $P(n)$ is true for every integer $n\ge n_0$ .

Not in the formula booklet: learn it.

A base case at $n=3$ can start a proof for all integers $n\ge3$ ; it does not establish the missing cases $1$ and $2$ . Equally, a proof of “ $k$ implies $k+2$ ” starting at $1$ reaches only the odd positive integers unless another starting case is supplied.

Key idea

The base case proves where the chain starts. The inductive step proves that the chain has no missing link. Both are needed.

Keep the condition visible in your conclusion: “If the result is true for $n=k$ , it is true for $n=k+1$ . Since it is true for $n=1$ , it is true for all positive integers $n$ , by induction.” Adjust the first integer to the problem.

Proving a formula for sequence terms

A recurrence tells you how to move from one term to the next; induction checks that a proposed explicit formula makes exactly the same move.

You already know

A recurrence such as $u_{n+1}=3u_n+2$ , together with $u_1$ , defines successive terms. An explicit formula gives $u_n$ directly from $n$ . Use $3\times3^k=3^{k+1}$ when advancing the index.

Starting with $u_1=2$ , this recurrence gives $u_2=8$ , $u_3=26$ and $u_4=80$ . Each is one less than a power of $3$ . The given claim $u_n=3^n-1$ explains that pattern, but the proof must use the recurrence as well as these first terms.

Worked example 1: a recurrence with a constant addition

Question. The sequence $(u_n)$ is defined by $u_1=2$ and $u_{n+1}=3u_n+2$ for integers $n\ge1$ . Prove by mathematical induction that $u_n=3^n-1$ for all positive integers $n$ .

Plan. Check the proposed first term, substitute the assumed expression for $u_k$ into the recurrence, and write the result in the required $k+1$ form.

3^1-1=2=u_1 \qquad \text{base case}

Assume $u_k=3^k-1$ for an arbitrary integer $k\ge1$ . Then

\begin{aligned} u_{k+1}&=3u_k+2 && \text{given recurrence} \\ &=3(3^k-1)+2 && \text{use the hypothesis} \\ &=3^{k+1}-3+2 && \text{expand} \\ &=3^{k+1}-1 && \text{required next form} \end{aligned}

Why this step? The recurrence gives a known expression for the next term. Substitution connects it to the assumed formula without assuming the formula for $k+1$ .

Answer. If the result holds for $n=k$ , it holds for $n=k+1$ . Since it holds for $n=1$ , $u_n=3^n-1$ for all positive integers $n$ , by induction.

Check. The formula gives $u_4=81-1=80$ ; the recurrence gives $3(26)+2=80$ .

Worked example 2 changes only the initial term. The recurrence stays the same, but its explicit formula needs a different coefficient. Check the supplied formula rather than carrying the old one across.

Worked example 2: a different starting term

Question. A sequence is defined by $v_1=4$ and $v_{n+1}=3v_n+2$ for integers $n\ge1$ . Prove that $v_n=5\times3^{n-1}-1$ for all positive integers $n$ .

Plan. Check $n=1$ , then substitute the full assumed expression, including its brackets, into the recurrence.

5\times3^{1-1}-1=5-1=4=v_1 \qquad \text{base case}

Assume $v_k=5\times3^{k-1}-1$ for an arbitrary integer $k\ge1$ . Then

\begin{aligned} v_{k+1}&=3v_k+2 && \text{given recurrence} \\ &=3(5\times3^{k-1}-1)+2 && \text{use the hypothesis} \\ &=5\times3^k-1 && \text{expand and combine} \\ &=5\times3^{(k+1)-1}-1 && \text{display the next index} \end{aligned}

Why this step? The final line shows exactly the stated formula with $n$ replaced by $k+1$ . An expression that merely looks similar needs this index comparison.

Answer. If the result holds for $n=k$ , it holds for $n=k+1$ . It holds for $n=1$ , so it holds for all positive integers $n$ , by induction.

Check. The recurrence gives $v_2=14$ and $v_3=44$ . The formula gives $5\times3^2-1=44$ when $n=3$ .

Neither sequence formula is in the formula booklet; the question supplies the result to prove. You are proving that it fits the initial condition and the recurrence, rather than learning it as a general formula for every sequence.

Watch out

Wrong: $3(5\times3^{k-1}-1)+2=15\times3^{k-1}+1$ . The outside $3$ multiplies the $-1$ too. Right: the constant terms are $-3+2=-1$ .

The next sequence changes the initial term once more. Keep the recurrence unchanged and make the dependence on $k+1$ explicit at the end.

Proving finite-sum formulae

The next partial sum contains every old term and exactly one new term, so isolate that final term before using the induction hypothesis.

For example, the sum of the first four squares is the sum of the first three squares plus $4^2$ : $30=14+16$ . In general, if $S_n=\sum_{r=1}^{n}a_r$ , then $S_{k+1}=S_k+a_{k+1}$ . This is what the summation notation means; it is not a separate formula supplied in the booklet.

Sums of squares and cubes

For every positive integer $n$ :

\begin{aligned} \sum_{r=1}^{n}r^2&=\frac{n(n+1)(2n+1)}{6} \\ \sum_{r=1}^{n}r^3&=\frac{n^2(n+1)^2}{4} \end{aligned}

In the formula booklet.

Having a formula available does not prove it. If the question asks for induction, establish the base case and show why adding the next term produces the next version of that formula.

Worked example 3: the sum of squares

Question. Prove by mathematical induction that $\displaystyle\sum_{r=1}^{n}r^2=\dfrac{n(n+1)(2n+1)}{6}$ for all positive integers $n$ .

Plan. Check $n=1$ , add $(k+1)^2$ to the assumed sum, and factor out $k+1$ .

\sum_{r=1}^{1}r^2=1=\frac{1(2)(3)}{6} \qquad \text{base case}

Assume $\sum_{r=1}^{k}r^2=\dfrac{k(k+1)(2k+1)}{6}$ for an arbitrary integer $k\ge1$ . Then

\begin{aligned} \sum_{r=1}^{k+1}r^2&=\sum_{r=1}^{k}r^2+(k+1)^2 && \text{split off the new term} \\ &=\frac{k(k+1)(2k+1)}{6}+(k+1)^2 && \text{use the hypothesis} \\ &=\frac{k+1}{6}\bigl(k(2k+1)+6(k+1)\bigr) && \text{common factor} \\ &=\frac{(k+1)(2k^2+7k+6)}{6} && \text{expand inside} \\ &=\frac{(k+1)(k+2)(2k+3)}{6} && \text{factorise} \\ &=\frac{(k+1)((k+1)+1)(2(k+1)+1)}{6} && \text{required next form} \end{aligned}

Why this step? Both terms contain $k+1$ . Taking it out leaves a quadratic that factors into the other two factors required by the next formula.

Answer. If the formula is true for $n=k$ , it is true for $n=k+1$ . It is true for $n=1$ , so it is true for all positive integers $n$ , by induction.

Check. At $n=4$ , the formula gives $4(5)(9)/6=30$ , agreeing with $1+4+9+16$ .

Worked example 4 changes only the power of each summand, from a square to a cube. The logical structure stays put; the new final term changes the factorisation.

Worked example 4: the sum of cubes

Question. Prove that $\displaystyle\sum_{r=1}^{n}r^3=\dfrac{n^2(n+1)^2}{4}$ for all positive integers $n$ .

Plan. Add $(k+1)^3$ to the assumed formula and take out the common factor $(k+1)^2/4$ .

\sum_{r=1}^{1}r^3=1=\frac{1^2(2)^2}{4} \qquad \text{base case}

Assume $\sum_{r=1}^{k}r^3=\dfrac{k^2(k+1)^2}{4}$ for an arbitrary integer $k\ge1$ . Then

\begin{aligned} \sum_{r=1}^{k+1}r^3&=\sum_{r=1}^{k}r^3+(k+1)^3 && \text{new final term} \\ &=\frac{k^2(k+1)^2}{4}+(k+1)^3 && \text{use the hypothesis} \\ &=\frac{(k+1)^2}{4}\bigl(k^2+4(k+1)\bigr) && \text{common factor} \\ &=\frac{(k+1)^2(k+2)^2}{4} && k^2+4k+4=(k+2)^2 \\ &=\frac{(k+1)^2((k+1)+1)^2}{4} && \text{required next form} \end{aligned}

Why this step? The entire bracket becomes a perfect square. That supplies the second squared factor in the formula with index $k+1$ .

Answer. If the formula is true for $n=k$ , it is true for $n=k+1$ . Since it is true for $n=1$ , it holds for all positive integers $n$ , by induction.

Check. At $n=3$ , $1+8+27=36$ and $3^2(4)^2/4=36$ .

Here is the lovely surprise hiding in the cube formula: the sum of the first $n$ cubes is the square of the sum of the first $n$ positive integers, because $\dfrac{n^2(n+1)^2}{4}=\left(\dfrac{n(n+1)}{2}\right)^2$ . For example, $1^3+2^3+3^3=(1+2+3)^2=36$ . The arithmetic-series formula used here is in the booklet; the induction proof explains why the cube identity holds for every positive integer.

Watch out

Wrong: $\sum_{r=1}^{k+1}r^2=\sum_{r=1}^{k}r^2+k^2+1$ . The new term is $(k+1)^2$ , not $k^2+1$ . Write the complete summand with $r=k+1$ before simplifying.

For the opening sum, putting $n=1000000$ into the proved square formula gives $333333833333500000$ . The last digit is easy to inspect; the reason it is the right number is the proof behind the formula. The next question changes the coefficient of the cube terms.

Proving matrix-power formulae

A matrix-power proof uses one more multiplication to turn the assumed whole matrix into the next whole matrix.

You already know

For a square matrix $\mathbf{A}$ , $\mathbf{A}^{k+1}=\mathbf{A}^k\mathbf{A}$ . Multiply rows by columns; keep the product order as written. A power of a matrix is not a power of each entry.

For $\mathbf{A}=\begin{pmatrix}1&2\\0&1\end{pmatrix}$ , direct multiplication gives $\mathbf{A}^2=\begin{pmatrix}1&4\\0&1\end{pmatrix}$ and $\mathbf{A}^3=\begin{pmatrix}1&6\\0&1\end{pmatrix}$ . The top-right entry grows in steps of $2$ . A proof has to show that this continues for every positive power, with all four entries correct.

Worked example 5: a changing off-diagonal entry

Question. Prove by induction that, for $\mathbf{A}=\begin{pmatrix}1&2\\0&1\end{pmatrix}$ ,

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

for all positive integers $n$ .

Plan. Substitute $n=1$ explicitly, assume the whole matrix formula at $k$ , then multiply it on the right by $\mathbf{A}$ .

\begin{pmatrix}1&2(1)\\0&1\end{pmatrix} =\begin{pmatrix}1&2\\0&1\end{pmatrix}=\mathbf{A}^1 \qquad \text{base case}

Assume $\mathbf{A}^k=\begin{pmatrix}1&2k\\0&1\end{pmatrix}$ for an arbitrary integer $k\ge1$ . Then

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

Why this step? The matrix product adds $2$ to the changing entry and leaves the other entries fixed. Showing the intermediate entries makes that mechanism visible.

Answer. If the formula holds for $n=k$ , it holds for $n=k+1$ . It holds for $n=1$ , so it holds for all positive integers $n$ , by induction.

Check. At $n=3$ , the top-right entry is $2(3)=6$ , agreeing with the direct cube above.

Worked example 6 changes only the common scale of the matrix: multiply every entry by $3$ . Repeated multiplication now contributes a scalar factor $3^n$ as well as the changing entry.

Worked example 6: keeping a scalar factor outside

Question. For $\mathbf{B}=\begin{pmatrix}3&6\\0&3\end{pmatrix}$ , prove that

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

for all positive integers $n$ .

Plan. Check the scaled formula at $1$ , then multiply the assumed matrix by $\mathbf{B}$ , keeping $3^k$ outside.

3^1\begin{pmatrix}1&2(1)\\0&1\end{pmatrix} =\begin{pmatrix}3&6\\0&3\end{pmatrix}=\mathbf{B}^1 \qquad \text{base case}

Assume $\mathbf{B}^k=3^k\begin{pmatrix}1&2k\\0&1\end{pmatrix}$ for an arbitrary integer $k\ge1$ . Then

\begin{aligned} \mathbf{B}^{k+1}&=\mathbf{B}^k\mathbf{B} && \text{one more factor} \\ &=3^k\begin{pmatrix}1&2k\\0&1\end{pmatrix}\begin{pmatrix}3&6\\0&3\end{pmatrix} && \text{use the hypothesis} \\ &=3^k\begin{pmatrix}3&6+6k\\0&3\end{pmatrix} && \text{rows by columns} \\ &=3^{k+1}\begin{pmatrix}1&2(k+1)\\0&1\end{pmatrix} && \text{factor out }3 \end{aligned}

Why this step? The new matrix multiplication supplies one additional factor of $3$ . Factoring it out gives exactly the scalar $3^{k+1}$ required by the next case.

Answer. If the formula holds for $n=k$ , it holds for $n=k+1$ . Since it holds for $n=1$ , it holds for all positive integers $n$ , by induction.

Check. Direct multiplication gives $\mathbf{B}^2=\begin{pmatrix}9&36\\0&9\end{pmatrix}=3^2\begin{pmatrix}1&4\\0&1\end{pmatrix}$ .

These particular matrix-power formulae are not in the formula booklet. The power identity $\mathbf{A}^{k+1}=\mathbf{A}^k\mathbf{A}$ follows from repeated multiplication; the question supplies the entry formula that you must prove.

Watch out

Wrong: $\begin{pmatrix}1&2\\0&1\end{pmatrix}^3=\begin{pmatrix}1&8\\0&1\end{pmatrix}$ . This cubes individual entries. Right: multiply matrices; the cube is $\begin{pmatrix}1&6\\0&1\end{pmatrix}$ .

For a given-answer proof, every intermediate equality matters. A correct final matrix alone leaves the inductive step unshown.

Exam tip

Show the base substitution, such as $2(1)=2$ , and an intermediate product before the final matrix. End with “If true for $k$ , then true for $k+1$ ” linked to the base case; merely declaring both cases true misses the conditional argument.

The final question changes only the scale from $3$ to $2$ . As with the million-term sum, the result can describe an enormous power while the proof uses just one small algebraic step.

Quick Recap

Check the first integer in the stated range, then assume the statement for one arbitrary integer $k$ .
A recurrence gives the next term; substitute the induction hypothesis into it.
A finite sum advances by adding the entire next summand, then factor into the required next-index form.
A matrix power advances by one matrix multiplication, with all entries and scalar factors included.
Finish with the conditional implication from $k$ to $k+1$ , connected to the verified starting case.

The opening sum is $1000000(1000001)(2000001)/6=333333833333500000$ . Induction justifies the formula for this sum and for every positive integer endpoint.

Last Accessed

Core Pure

Mechanics (Major and Minor)

Statistics (Major and Minor)

Modelling with Algorithms

Numerical Methods

Extra Pure

Further Pure with Technology

Pp4 - Induction for sequences, series and matrices

Why one step reaches every integer

Proving a formula for sequence terms

Proving finite-sum formulae

Proving matrix-power formulae

Quick Recap

Learn faster with Nova