FP1 January 2012 Q7
7. A sequence can be described by the recurrence formula \[u_{n+1} = 2u_n + 1, \qquad n \geqslant 1,\ \ u_1 = 1\]
(a) Find \(u_2\) and \(u_3\). (2)
(b) Prove by induction that \(u_n = 2^n - 1\) (5)
| Scheme | Marks |
|---|---|
| \(u_2 = 3,\ u_3 = 7\) | B1, B1 |
| (2) |
| Scheme | Marks |
|---|---|
| At \(n = 1\), \(u_1 = 2^1 - 1 = 1\) and so result true for \(n = 1\) | B1 |
| Assume true for \(n = k\); \(u_k = 2^k - 1\) | |
| and so \(u_{k+1}\ (= 2u_k + 1) = 2(2^k - 1) + 1\) Substitutes \(u_k\) into \(u_{k+1}\) (must see this line) Correct expression | M1 A1 |
| \(u_{k+1}\ (= 2^{k+1} - 2 + 1) = 2^{k+1} - 1\) Correct completion to \(u_{k+1} = 2^{k+1} - 1\) | A1 |
| Must see 4 things: true for \(n = 1\), assumption true for \(n = k\), said true for \(n = k + 1\) and therefore true for all \(n\) Fully complete proof with no errors and comment. All the previous marks in (b) must have been scored. | A1cso |
| (5) | |
| (7 marks) |
Notes
Ignore any subsequent attempts e.g. \(u_{k+2} = 2u_{k+1} + 1 = 2(2^{k+1} - 1) + 1\) etc.