CP-1 Proof — revision question pack

1 specification points · notes, questions, answers and worked methods

Checked against Edexcel 9FM0 section CP-1. Review basis: the qualification registry sourced from the Pearson Edexcel Level 3 Advanced GCE in Further Mathematics (9FM0) specification; registry verification recorded 17 July 2026.

How this checking works

CP-1.1 · Construct proofs using mathematical induction. Contexts include sums of series, divisibility and powers of matrices.

Explanation

Mathematical induction proves a statement $P(n)$ for every integer from a stated starting value. First verify the base case.
Then assume $P(k)$ is true for an arbitrary permitted integer $k$ ; this is the induction hypothesis. Use that hypothesis to derive $P(k+1)$ , rather than assuming the next case.
For a series, add the term with index $k+1$ ; for divisibility, expose the required integer factor; for a matrix power, multiply the assumed expression for $A^k$ by $A$ .
The conclusion must state that the base case and inductive implication together prove $P(n)$ for all integers in the stated range.
Checking several cases alone is not a proof.

The four linked stages of a proof by mathematical induction.

Worked example

Prove by mathematical induction that $5^{2n}-1$ is divisible by $24$ for every positive integer $n$ .

1.For $n=1$ , $5^2-1=24$ , so the base case is divisible by $24$ .
2.Assume $5^{2k}-1=24m$ for some positive integer $k$ and some integer $m$ .
3. $5^{2(k+1)}-1=25\left(5^{2k}-1\right)+24$ .
4.Substitution gives $5^{2(k+1)}-1=24(25m+1)$ , which is divisible by $24$ because $25m+1$ is an integer.
5.Therefore $5^{2n}-1$ is divisible by $24$ for every positive integer $n$ .

Answer: The base case holds and $P(k)\Rightarrow P(k+1)$ , so the divisibility result follows by mathematical induction.

Common mistakes

Don't fall into the trap of assuming the statement for $k+1$ , which makes the inductive step circular.
Don't fall into the trap of writing only that the result is a multiple of $24$ without expressing the remaining factor as an integer.
Don't fall into the trap of checking several numerical values and treating those examples as a proof for all positive integers.

Exam tip

A proof-by-induction response must show the base case, use the named induction hypothesis in the $k+1$ case, and finish with a quantified conclusion.

Tier 1 · Easy

1.
Prove by mathematical induction that $1+3+5+\cdots+(2n-1)=n^2$ for every positive integer $n$ .
(4)
(Total for Question 1 is 4 marks)
2.
Prove by mathematical induction that $\displaystyle\sum_{r=1}^{n}\frac{1}{r(r+1)}=\frac{n}{n+1}$ for every positive integer $n$ .
(5)
(Total for Question 2 is 5 marks)

Tier 2 · Standard

1.
Prove by mathematical induction that $8^n-1$ is divisible by $7$ for every positive integer $n$ .
(5)
(Total for Question 1 is 5 marks)
2.
Prove by mathematical induction that $n^3+5n$ is divisible by $6$ for every positive integer $n$ .
(6)
(Total for Question 2 is 6 marks)
3.
For positive integers $n$ , use mathematical induction to prove that $\displaystyle\sum_{r=1}^{n}r2^r=(n-1)2^{n+1}+2$ .
(6)
(Total for Question 3 is 6 marks)

Tier 3 · Hard

1.
Let $A=\begin{pmatrix}2&1\\0&2\end{pmatrix}$ . Prove by mathematical induction that $A^n=\begin{pmatrix}2^n&n2^{n-1}\\0&2^n\end{pmatrix}$ for every positive integer $n$ .
(6)
(Total for Question 1 is 6 marks)
2.
Let $A=\begin{pmatrix}0&-1\\1&2\end{pmatrix}$ . Prove by mathematical induction that $A^n=\begin{pmatrix}1-n&-n\\n&n+1\end{pmatrix}$ for every positive integer $n$ .
(6)
(Total for Question 2 is 6 marks)
3.
A sequence satisfies $u_1=5$ and $u_{n+1}=\lambda u_n+\mu$ for $n\geq1$ , where $\lambda$ and $\mu$ are real constants. Given that $u_2=13$ and $u_3=29$ , find the value of $\lambda$ and the value of $\mu$ . Prove by mathematical induction that $u_n=2^{n+2}-3$ for every positive integer $n$ .
(7)
(Total for Question 3 is 7 marks)
4.
A sequence is defined by $u_1=5$ , $u_2=13$ and $u_{n+2}=5u_{n+1}-6u_n$ for $n\geq1$ . Prove by mathematical induction that $u_n=2^n+3^n$ for every positive integer $n$ .
(7)
(Total for Question 4 is 7 marks)
5.
The Fibonacci sequence is defined by $F_1=1$ , $F_2=1$ and $F_{n+2}=F_{n+1}+F_n$ for $n\geq1$ . Let $A=\begin{pmatrix}1&1\\1&0\end{pmatrix}$ . Prove by mathematical induction that $A^n=\begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix}$ for every integer $n\geq2$ . Hence find the least value of $n$ for which the top-left entry of $A^n$ is greater than $2000$ .
(8)
(Total for Question 5 is 8 marks)

Answer key

Answers begin on a new printed page so the question pack can be completed without the solutions alongside it.

CP-1.1 · Construct proofs using mathematical induction. Contexts include sums of series, divisibility and powers of matrices.

Tier 1 · Easy

Mark scheme for CP-1.1 Tier 1 · Easy
Question	Scheme	Marks
1	Base case: when $n=1$ , both sides equal $1$ . Assume $1+3+\cdots+(2k-1)=k^2$ for some positive integer $k$ . Then $1+3+\cdots+(2k-1)+(2k+1)=k^2+2k+1=(k+1)^2$ . Therefore the result holds for every positive integer $n$ by induction.	4
(4 marks)		4
Notes
Verify $n=1$ . For the inductive step, the next odd number is $2(k+1)-1=2k+1$ . Add it to the assumed sum: $k^2+(2k+1)=(k+1)^2$ , which is exactly the required form for $n=k+1$ . Complete the induction conclusion.
2	For $n=1$ , the left side is $1/(1\cdot2)=1/2$ , which equals the right side. Assume $\displaystyle\sum_{r=1}^{k}\frac{1}{r(r+1)}=\frac{k}{k+1}$ for an arbitrary positive integer $k$ . $\displaystyle\sum_{r=1}^{k+1}\frac{1}{r(r+1)}=\frac{k}{k+1}+\frac{1}{(k+1)(k+2)}$ . Combining the fractions gives $\dfrac{k(k+2)+1}{(k+1)(k+2)}=\dfrac{(k+1)^2}{(k+1)(k+2)}=\dfrac{k+1}{k+2}$ . Therefore the identity holds for every positive integer $n$ by mathematical induction.	5
(5 marks)		5
Notes
Verify the base case $n=1$ . Assume the identity at $n=k$ , then append the term with index $k+1$ . The induction hypothesis gives $k/(k+1)+1/((k+1)(k+2))$ . Its numerator is $k(k+2)+1=(k+1)^2$ , so the sum simplifies to $(k+1)/(k+2)$ , which is the required form at $k+1$ . The base case and inductive implication complete the proof.

Tier 2 · Standard

Mark scheme for CP-1.1 Tier 2 · Standard
Question	Scheme	Marks
1	Base case: $8^1-1=7$ , which is divisible by $7$ . Assume $8^k-1=7m$ for some integer $m$ . $8^{k+1}-1=8(8^k-1)+7=7(8m+1)$ . Since $8m+1$ is an integer, $8^{k+1}-1$ is divisible by $7$ . Therefore the result holds for every positive integer $n$ by induction.	5
(5 marks)		5
Notes
After the base case, express the hypothesis as $8^k-1=7m$ with $m\in\mathbb Z$ . Rewrite the next case so the hypothesis appears: $8^{k+1}-1=8(8^k-1)+7$ . Substitution gives $7(8m+1)$ , an integer multiple of $7$ , so the inductive step and conclusion follow.
2	For $n=1$ , $n^3+5n=1+5=6$ , which is divisible by $6$ . Assume $k^3+5k=6m$ for an arbitrary positive integer $k$ and some integer $m$ . $(k+1)^3+5(k+1)=k^3+5k+3k(k+1)+6$ . Since $k(k+1)$ is even, write $k(k+1)=2q$ for an integer $q$ . The next expression is $6m+6q+6=6(m+q+1)$ , so it is divisible by $6$ . Therefore $n^3+5n$ is divisible by $6$ for every positive integer $n$ .	6
(6 marks)		6
Notes
The domain begins at $1$ , so verify $1^3+5(1)=6$ . Write the induction hypothesis as $k^3+5k=6m$ . The difference between the next expression and the assumed one is $3k^2+3k+6=3k(k+1)+6$ . Consecutive integers have an even product, so write $k(k+1)=2q$ with $q\in\mathbb Z$ . The next expression is then $6m+6q+6$ , an integer multiple of $6$ , completing the induction step and quantified conclusion.
3	For $n=1$ , the left side is $2$ and the right side is $(1-1)2^2+2=2$ . For an arbitrary positive integer $k$ , assume $(k-1)2^{k+1}+2=\displaystyle\sum_{r=1}^{k}r2^r$ . $\displaystyle\sum_{r=1}^{k+1}r2^r=2^{k+1}[(k-1)+(k+1)]+2$ . The bracket is $2k$ , so the sum is $2k\cdot2^{k+1}+2$ . This is $k\cdot2^{k+2}+2=((k+1)-1)2^{(k+1)+1}+2$ . The verified base case and inductive implication establish the formula for all positive integers $n$ .	6
(6 marks)		6
Notes
Verify the formula at $n=1$ . Assume it at $n=k$ , then append the term $(k+1)2^{k+1}$ . The two coefficients of $2^{k+1}$ add to $(k-1)+(k+1)=2k$ , so the new sum is $k\cdot2^{k+2}+2$ , exactly the claimed expression with $k+1$ in place of $n$ .

Tier 3 · Hard

Mark scheme for CP-1.1 Tier 3 · Hard
Question	Scheme	Marks
1	Base case: the stated formula gives $A^1=\begin{pmatrix}2&1\\0&2\end{pmatrix}$ . Assume $A^k=\begin{pmatrix}2^k&k2^{k-1}\\0&2^k\end{pmatrix}$ . $A^{k+1}=A^kA=\begin{pmatrix}2^{k+1}&2^k+k2^k\\0&2^{k+1}\end{pmatrix}$ . The upper-right entry is $(k+1)2^k$ , so this is the required formula with $k+1$ in place of $n$ . Therefore the result holds for every positive integer $n$ by induction.	6
(6 marks)		6
Notes
Check $n=1$ , including the upper-right entry $1\cdot2^0=1$ . Assume the formula for $A^k$ and multiply on the right by $A$ . The upper-right entry is $2^k\cdot1+k2^{k-1}\cdot2=(k+1)2^k$ ; the diagonal entries are $2^{k+1}$ . This matches the target at $k+1$ , completing the proof.
2	For $n=1$ , the proposed matrix is $\begin{pmatrix}0&-1\\1&2\end{pmatrix}=A$ . Assume $A^k=\begin{pmatrix}1-k&-k\\k&k+1\end{pmatrix}$ for an arbitrary positive integer $k$ . $A^{k+1}=A^kA=\begin{pmatrix}1-k&-k\\k&k+1\end{pmatrix}\begin{pmatrix}0&-1\\1&2\end{pmatrix}$ . Multiplication gives $A^{k+1}=\begin{pmatrix}-k&-(k+1)\\k+1&k+2\end{pmatrix}$ . This is the stated form with $k+1$ in place of $n$ . Therefore the formula holds for every positive integer $n$ by mathematical induction.	6
(6 marks)		6
Notes
Check the base case entry by entry. For the inductive step, multiply $A^k$ by $A$ , so $A^{k+1}=A^kA$ . Multiplication gives entries $-k$ , $-(k+1)$ , $k+1$ and $k+2$ , exactly $1-(k+1)$ , $-(k+1)$ , $k+1$ and $(k+1)+1$ . Thus the induction hypothesis produces the required next power, and the quantified conclusion follows.
3	$5\lambda+\mu=13$ and $13\lambda+\mu=29$ . Solving the simultaneous equations gives $\lambda=2$ and $\mu=3$ . For $n=1$ , $2^{1+2}-3=5=u_1$ . Assume $u_k=2^{k+2}-3$ for an arbitrary positive integer $k$ . Using the recurrence, $u_{k+1}=2(2^{k+2}-3)+3$ . Simplifying gives $u_{k+1}=2^{k+3}-3=2^{(k+1)+2}-3$ . The base case and the implication $P(k)\Rightarrow P(k+1)$ establish $u_n=2^{n+2}-3$ for all positive integers $n$ .	7
(7 marks)		7
Notes
The two supplied recurrence steps give simultaneous equations whose difference is $8\lambda=16$ , hence $\lambda=2$ and $\mu=3$ . Check the base case. Under the induction hypothesis, substitute the claimed $u_k$ into $u_{k+1}=2u_k+3$ , simplify the exponential and constant terms separately, and match the result to the formula at $k+1$ .
4	For $n=1$ , $2^1+3^1=5=u_1$ . For $n=2$ , $2^2+3^2=13=u_2$ . For an arbitrary positive integer $k$ , assume $u_k=2^k+3^k$ and $u_{k+1}=2^{k+1}+3^{k+1}$ . $u_{k+2}=5(2^{k+1}+3^{k+1})-6(2^k+3^k)$ . The powers of $2$ simplify to $5(2^{k+1})-6(2^k)=2^{k+2}$ . The powers of $3$ simplify to $5(3^{k+1})-6(3^k)=3^{k+2}$ , so $u_{k+2}=2^{k+2}+3^{k+2}$ . The two base cases and the inductive implication prove the formula for every positive integer $n$ .	7
(7 marks)		7
Notes
A second-order recurrence needs two base cases and a two-term induction hypothesis. Substitute the claimed forms for $u_k$ and $u_{k+1}$ into the recurrence. Factoring $2^k$ and $3^k$ separately produces $2^{k+2}$ and $3^{k+2}$ , which is the required expression for the next term.
5	For $n=2$ , $A^2=\begin{pmatrix}2&1\\1&1\end{pmatrix}=\begin{pmatrix}F_3&F_2\\F_2&F_1\end{pmatrix}$ . Assume $A^k=\begin{pmatrix}F_{k+1}&F_k\\F_k&F_{k-1}\end{pmatrix}$ for an arbitrary integer $k\geq2$ . $A^{k+1}=A^kA=\begin{pmatrix}F_{k+1}+F_k&F_{k+1}\\F_k+F_{k-1}&F_k\end{pmatrix}$ . Using the Fibonacci recurrence, this is $\begin{pmatrix}F_{k+2}&F_{k+1}\\F_{k+1}&F_k\end{pmatrix}$ . The base case and inductive implication prove the stated matrix formula for every integer $n\geq2$ . The top-left entry of $A^n$ is $F_{n+1}$ . $F_{17}=1597$ and $F_{18}=2584$ . The Fibonacci sequence is increasing from $F_2$ onwards, so the least value is $n=17$ .	8
(8 marks)		8
Notes
Verify the matrix identity at $n=2$ . Multiply the assumed expression for $A^k$ on the right by $A$ and use the Fibonacci recurrence in both rows to obtain the required expression for $A^{k+1}$ . The proved top-left entry is $F_{n+1}$ ; compare the consecutive values $F_{17}$ and $F_{18}$ and use monotonicity to justify the least index.