| Exam Board | Edexcel |
|---|---|
| Module | FP1 (Further Pure Mathematics 1) |
| Year | 2010 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Proof by induction |
| Type | Prove divisibility |
| Difficulty | Standard +0.8 This is a two-part induction proof requiring students to first establish a recurrence relation, then use it in a divisibility proof. The recurrence relation derivation requires algebraic manipulation that isn't immediately obvious, and the inductive step involves handling the expression 6f(k) - 4(2^k) with careful attention to factor extraction. While induction is a standard FP1 topic, this question demands more insight than routine 'prove the formula' inductions, placing it moderately above average difficulty. |
| Spec | 4.01a Mathematical induction: construct proofs |
| Answer | Marks | Guidance |
|---|---|---|
| (a) LHS \(= f(k+1) = 2^{k+1} + 6^{k+1} = 2(2^k) + 6(6^k) = 6(2^k + 6^k) - 4(2^k) = 6f(k) - 4(2^k)\) | M1, A1, A1 | |
| OR RHS \(= 6f(k) - 4(2^k) = 6(2^k + 6^k) - 4(2^k) = 2(2^k) + 6(6^k) = 2^{k+1} + 6^{k+1} = f(k+1)\) (marked as \(*\)) | (3 marks) | |
| OR \(f(k+1) - 6f(k) = 2^{k+1} + 6^{k+1} - 6(2^k + 6^k) = (2-6)(2^k) = -4 \cdot 2^k\), and so \(f(k+1) = 6f(k) - 4(2^k)\) | M1, A1, A1 | (3 marks) |
| (b) \(n = 1: f(1) = 2^1 + 6^1 = 8\), which is divisible by \(8\) | B1 | |
| Either: Assume \(f(k)\) divisible by \(8\) and try to use \(f(k+1) = 6f(k) - 4(2^k)\) | M1 | |
| Show \(4(2^k) = 4 \times 2(2^{k-1}) = 8(2^{k-1})\) or \(8(:2^k)\). Or valid statement. Deduction that result is implied for \(n = k+1\) and so is true for positive integers by induction (may include \(n = 1\) true here) | A1, A1 cso | (4 marks) |
| Or: Assume \(f(k)\) divisible by \(8\) and try to use \(f(k+1) - f(k)\) or \(f(k+1) + f(k)\) including factorising \(6^k = 2^k 3^k = 2^2 3^k = 2^2 3^k (1 + 5 \cdot 3^k)\) or \(= 2^2 2^{k-3}(3 + 7.3^k)\) o.e. Deduction that result is implied for \(n = k+1\) and so is true for positive integers by induction (must include explanation of why \(n = 2\) is also true here) | M1, A1, A1 cso | (4 marks) |
**(a)** LHS $= f(k+1) = 2^{k+1} + 6^{k+1} = 2(2^k) + 6(6^k) = 6(2^k + 6^k) - 4(2^k) = 6f(k) - 4(2^k)$ | **M1, A1, A1** |
OR RHS $= 6f(k) - 4(2^k) = 6(2^k + 6^k) - 4(2^k) = 2(2^k) + 6(6^k) = 2^{k+1} + 6^{k+1} = f(k+1)$ (marked as $*$) | | (3 marks)
OR $f(k+1) - 6f(k) = 2^{k+1} + 6^{k+1} - 6(2^k + 6^k) = (2-6)(2^k) = -4 \cdot 2^k$, and so $f(k+1) = 6f(k) - 4(2^k)$ | **M1, A1, A1** | (3 marks)
**(b)** $n = 1: f(1) = 2^1 + 6^1 = 8$, which is divisible by $8$ | **B1** |
Either: Assume $f(k)$ divisible by $8$ and try to use $f(k+1) = 6f(k) - 4(2^k)$ | **M1** |
Show $4(2^k) = 4 \times 2(2^{k-1}) = 8(2^{k-1})$ or $8(:2^k)$. Or valid statement. Deduction that result is implied for $n = k+1$ and so is true for positive integers by induction (may include $n = 1$ true here) | **A1, A1 cso** | (4 marks)
Or: Assume $f(k)$ divisible by $8$ and try to use $f(k+1) - f(k)$ or $f(k+1) + f(k)$ including factorising $6^k = 2^k 3^k = 2^2 3^k = 2^2 3^k (1 + 5 \cdot 3^k)$ or $= 2^2 2^{k-3}(3 + 7.3^k)$ o.e. Deduction that result is implied for $n = k+1$ and so is true for positive integers by induction (must include explanation of why $n = 2$ is also true here) | **M1, A1, A1 cso** | (4 marks)
**Total: 7 marks**
**Guidance:**
(a) M1: for substitution into LHS (or RHS) or $f(k+1) - 6f(k)$. A1: for correct split of the two separate powers. A1: for completion of proof with no error or ambiguity (needs (for example) to start with one side of equation and reach the other or show that each side separately is $2(2^k) + 6(6^k)$ and **conclude LHS = RHS**)
(b) B1: for substitution of $n = 1$ and stating "true for $n = 1$" or "divisible by 8" or tick. (This statement may appear in the concluding statement of the proof)
M1: Assume $f(k)$ divisible by $8$ and consider $f(k+1) = 6f(k) - 4(2^k)$ or equivalent expression that could lead to proof – not merely $f(k+1) - f(k)$ unless deduce that $2$ is a factor of $6$ (see right hand scheme above).
A1: Indicates each term divisible by $8$ OR takes out factor $8$ or $2^3$
A1: Induction statement. Statement $n = 1$ here could contribute to B1 mark earlier.
**NB:** $f(k+1) - f(k) = 2^{k+1} - 2^k + 6^{k+1} - 6^k = 2^k + 5 \cdot 6^k$ only is **M0 A0 A0**
**(b) "Otherwise" methods**
Could use: $f(k+1) = 2f(k) + 4(6^k)$ or $f(k+2) = 36f(k) - 32(6^k)$ or $f(k+2) = 4f(k) + 32(2^k)$ in a similar way to given expression and Left hand mark scheme is applied.
**Special Case:** Otherwise Proof not involving induction: This can only be awarded the **B1** for checking $n = 1$.
---7.
$$f ( n ) = 2 ^ { n } + 6 ^ { n }$$
\begin{enumerate}[label=(\alph*)]
\item Show that $\mathrm { f } ( k + 1 ) = 6 \mathrm { f } ( k ) - 4 \left( 2 ^ { k } \right)$.
\item Hence, or otherwise, prove by induction that, for $n \in \mathbb { Z } ^ { + } , \mathrm { f } ( n )$ is divisible by 8 .
\end{enumerate}
\hfill \mbox{\textit{Edexcel FP1 2010 Q7 [7]}}