AS June 2018 Paper 1 Q7
7 Prove by induction that \(2^{n+1} + 5 \times 9^n\) is divisible by 7 for all integers \(n \geqslant 1\). [6]
| Scheme | Marks | AO |
|---|---|---|
| \(k = 1\), 49 is divisible by 7 | M1 | 2.1 |
| Assume true for \(n = k\) i.e. that \(2^{k+1} + 5 \times 9^k\) is divisible by 7 oe | M1 | 2.1 |
| Considering \(2^{k+1+1} + 5 \times 9^{k+1}\) and rewriting the first term as \(2 \times 2^{k+1}\) or the second term as \(9 \times 5 \times 9^k\) | M1 | 1.1 |
| \(2(7p - 5 \times 9^k) + 9 \times 5 \times 9^k\) or \(2 \times 2^{k+1} + 9(7p - 2^{k+1})\) | M1 | 1.1 |
| \(7(2p + 5 \times 9^k)\) or \(7(9p - 2^{k+1})\) (which is divisible by 7) | A1 | 2.2a |
| So true for \(n = k \Rightarrow\) true for \(n = k + 1\). But true for \(n = 1\). So true for all positive integers \(n \geqslant 1\) | E1 | 2.4 |
| [6] |
Notes
M1: (1st) Basis case. Must explicitly state divisibility (\(49 \div 7 = 7\) is OK).
Do not condone \(k = 0\) unless later stated \(1 \gt 0\)
M1: (2nd) Statement of inductive hypothesis. Allow “\(= 7p\)” without further qualification.
M1: (3rd) Might not all be done before next step. Do not allow if e.g. \(45^k\).
Needs to have a \(2^{k+1}\) or \(5 \times 9^k\) so that the \(n = k\) case can be used.
M1: (4th) Uses inductive hypothesis properly. Do not allow if e.g. \(45^k\).
Do not allow M1 if both replacements made unless recovered later
A1: Simplification with sufficient working to establish divisibility for \(k + 1\)
E1: Clear conclusion for induction process.
A formal proof by induction is required for full marks.