| Exam Board | CAIE |
|---|---|
| Module | Further Paper 1 (Further Paper 1) |
| Year | 2020 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Proof by induction |
| Type | Prove recurrence relation formula |
| Difficulty | Standard +0.3 Part (a) is a standard induction proof with a straightforward recurrence relation requiring routine algebraic manipulation. Part (b) requires minimal additional insight—substituting the formula and factoring. This is slightly easier than average for Further Maths, as the induction follows a template and the deduction is direct. |
| Spec | 4.01a Mathematical induction: construct proofs |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(u_1 = 1 = 2^1 - 1\) | B1 | |
| Assume true for \(n = k\), so \(u_k = 2^k - 1\) | B1 | |
| Then \(u_{k+1} = 2(2^k - 1) + 1 = 2^{k+1} - 1\) | M1 A1 | |
| So it is also true for \(n = k+1\). Hence, by induction, true for all positive integers. | A1 | |
| Total | 5 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(\dfrac{u_{2n}}{u_n} = \dfrac{2^{2n}-1}{2^n - 1} = \dfrac{(2^n-1)(2^n+1)}{(2^n-1)} = 2^n + 1\) | M1 A1 | |
| Total | 2 |
## Question 2:
**Part (a)**
| Answer | Marks | Guidance |
|--------|-------|----------|
| $u_1 = 1 = 2^1 - 1$ | B1 | |
| Assume true for $n = k$, so $u_k = 2^k - 1$ | B1 | |
| Then $u_{k+1} = 2(2^k - 1) + 1 = 2^{k+1} - 1$ | M1 A1 | |
| So it is also true for $n = k+1$. Hence, by induction, true for all positive integers. | A1 | |
| **Total** | **5** | |
**Part (b)**
| Answer | Marks | Guidance |
|--------|-------|----------|
| $\dfrac{u_{2n}}{u_n} = \dfrac{2^{2n}-1}{2^n - 1} = \dfrac{(2^n-1)(2^n+1)}{(2^n-1)} = 2^n + 1$ | M1 A1 | |
| **Total** | **2** | |2 The sequence $u _ { 1 } , u _ { 2 } , u _ { 3 } , \ldots$ is such that $u _ { 1 } = 1$ and $\mathrm { u } _ { \mathrm { n } + 1 } = 2 \mathrm { u } _ { \mathrm { n } } + 1$ for $n \geqslant 1$.
\begin{enumerate}[label=(\alph*)]
\item Prove by induction that $u _ { n } = 2 ^ { n } - 1$ for all positive integers $n$.
\item Deduce that $\mathrm { u } _ { 2 \mathrm { n } }$ is divisible by $\mathrm { u } _ { \mathrm { n } }$ for $n \geqslant 1$.
\end{enumerate}
\hfill \mbox{\textit{CAIE Further Paper 1 2020 Q2 [7]}}