| Exam Board | OCR |
|---|---|
| Module | Further Additional Pure AS (Further Additional Pure AS) |
| Year | 2021 |
| Session | November |
| Marks | 6 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Proof by induction |
| Type | Prove sequence property via recurrence |
| Difficulty | Standard +0.8 This is a two-part Fibonacci induction problem from Further Pure AS. Part (a) requires algebraic manipulation of the recurrence relation (straightforward but non-trivial). Part (b) is a standard strong induction proof showing F_{3n} is even, requiring careful setup with the recurrence and the result from (a). While induction is A-level content, applying it to Fibonacci with index manipulation elevates this above average difficulty, though it follows a recognizable pattern once the structure is understood. |
| Spec | 4.01a Mathematical induction: construct proofs8.01e Fibonacci: and related sequences (e.g. Lucas numbers) |
| Answer | Marks | Guidance |
|---|---|---|
| 3 | (a) | F = F + F = (F + F ) + F |
| Answer | Marks |
|---|---|
| 3k + 1 3k | M1 |
| Answer | Marks |
|---|---|
| [2] | 2.1 |
| 1.1 | Use of Fibonacci r.r. twice |
| Answer | Marks |
|---|---|
| (b) | Since F = F = 2 is even, the result is true for n = 1 |
| Answer | Marks |
|---|---|
| whenever true for n, proof follows by induction | B1 |
| Answer | Marks |
|---|---|
| [4] | 1.1 |
| Answer | Marks |
|---|---|
| 2.4 | It must be made clear, somewhere, what “assume the result is |
Question 3:
3 | (a) | F = F + F = (F + F ) + F
3k + 3 3k + 2 3k + 1 3k + 1 3k 3k + 1
= 2F + F
3k + 1 3k | M1
A1
[2] | 2.1
1.1 | Use of Fibonacci r.r. twice
AG
(b) | Since F = F = 2 is even, the result is true for n = 1
3 3×1
Assuming that F is even for some k (≥ 1)
3k
F = even + even = even also
3k + 3
Since result is true for n = 1 and true for n + 1
whenever true for n, proof follows by induction | B1
M1
A1
B1
[4] | 1.1
2.1
2.2a
2.4 | It must be made clear, somewhere, what “assume the result is
true for n = k” means; and must include identification that
F = F is the case for n = k + 1 at some stage
3k + 3 3(k + 1)
Use of (a)’s result, clearly made
Carefully explained induction conclusion3 For positive integers $n$, the sequence of Fibonacci numbers, $\left\{ \mathrm { F } _ { \mathrm { n } } \right\}$, starts with the terms $F _ { 1 } = 1 , F _ { 2 } = 1 , F _ { 3 } = 2 , \ldots$ and is given by the recurrence relation $\mathrm { F } _ { \mathrm { n } } = \mathrm { F } _ { \mathrm { n } - 1 } + \mathrm { F } _ { \mathrm { n } - 2 } ( \mathrm { n } \geqslant 3 )$.
\begin{enumerate}[label=(\alph*)]
\item Show that $\mathrm { F } _ { 3 \mathrm { k } + 3 } = 2 \mathrm {~F} _ { 3 \mathrm { k } + 1 } + \mathrm { F } _ { 3 \mathrm { k } }$, where $k$ is a positive integer.
\item Prove by induction that $\mathrm { F } _ { 3 n }$ is even for all positive integers $n$.
\end{enumerate}
\hfill \mbox{\textit{OCR Further Additional Pure AS 2021 Q3 [6]}}