CP-1 Proof — coverage pack

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

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

Mathematical induction proves a statement $P(n)$ for every integer from a stated starting value: verify the base case, assume $P(k)$ , prove $P(k+1)$ , then conclude.
In the inductive step, use the hypothesis explicitly: add the next term for a sum, isolate a multiple for divisibility, or multiply by the matrix once more for a matrix power.
For example, after assuming a sum formula for $S_k$ , write $S_{k+1}=S_k+$ the term with index $k+1$ , then simplify to the target formula with $k+1$ substituted for $n$ .
A common error is circular reasoning: assuming the result for $k+1$ , or checking several numerical cases, does not prove the result for all permitted integers.

Tier 1 · Easy

1. Prove by mathematical induction that $1+3+5+\cdots+(2n-1)=n^2$ for every positive integer $n$ .[4 marks]
Answer
- 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.
Method: 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.

Tier 2 · Standard

1. Prove by mathematical induction that $8^n-1$ is divisible by $7$ for every positive integer $n$ .[5 marks]
Answer
- 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.
Method: 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.

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 marks]
Answer
- 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.
Method: 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.