Challenging +1.8 This is a Further Maths question requiring proof by induction and manipulation of recurrence relations. Part (i) needs systematic expansion of the Fibonacci recurrence over multiple steps, while part (ii) requires recognizing that strong induction combined with the result from (i) establishes divisibility. The multi-step algebraic manipulation and formal proof structure place this well above average difficulty, though it follows a relatively standard induction pattern once the approach is identified.
6 The Fibonacci sequence \(\left\{ F _ { n } \right\}\) is defined by \(F _ { 0 } = 0 , F _ { 1 } = 1\) and \(F _ { n } = F _ { n - 1 } + F _ { n - 2 }\) for all \(n \geqslant 2\).
Show that \(F _ { n + 5 } = 5 F _ { n + 1 } + 3 F _ { n }\)
Prove that \(F _ { n }\) is a multiple of 5 when \(n\) is a multiple of 5 .
Since the result is true for n = 0 (allow n = 5) &
true for n = 5k true for n = 5(k + 1)
it follows that the result is true for all non-
Answer
Marks
negative (allow “positive”) integers n
B1
B1
M1
A 1
Answer
Marks
E1
1.1a
2.1
3.1a
2 . 5
Answer
Marks
2.4
Allow F = 5 as a baseline case
5
Use of (i)’s result
Only given if all 4 other marks
Answer
Marks
earned
E0 for those who fail to
distinguish between “n” and
“5n” in their explanation
[5]
Alt. Consider {F } modulo 5:
n
F = 0, F = 1 F = 1, F = 2, F = 3, F = 0,
0 1 2 3 4 5
F = 3, F = 3, F = 1, F = 4, F = 0,
6 7 8 9 10
F = 4, F = 4, F = 3, F = 2, F = 0,
11 12 13 14 15
F = 2, F = 2, F = 4, F = 1, F = 0, F = 1
16 17 18 19 20 21
Since {F } is given by a second-order, linear,
n
homogeneous r.r. and F = F = 0, and
0 20
F = F = 1, it follows that the sequence mod 5
1 21
is periodic with period 20
As F , F , F and F are all 0 (mod 5) and the
0 5 10 15
sequence repeats every 20 terms, it follows that
F 0 (mod 5) for all integers n = 0, 1, 2, …
Answer
Marks
5n
Note that there are only
5P = 5 × 4 = 20
2
pairs of the five possible residues
mod 5; thus the maximum period of
the sequence{F mod 5} is 20.
n
Question 6:
6 | (i) | F = F + F = (F + F ) + F
n + 5 n + 4 n + 3 n + 3 n + 2 n + 3
= 2F + F
n + 3 n + 2
= 2(F + F ) + F
n + 2 n + 1 n + 2
= 3F + 2F
n + 2 n + 1
= 3(F + F ) + 2F
n + 1 n n + 1
= 5F + 3F
n + 1 n | M1
M 1
A1 | 3.1a
1.1
1.1 | Using (not just stating) Fibonacci r.r.
at least twice (up or down)
Use of Fibonacci r.r. all the way to
F and F
n + 1 n
[3]
(ii) | F = 0 which is divisible by 5
0
Assume that F is divisible by 5
5k
Then F = 5F + 3F
5k + 5 5k + 1 5k
which is the sum of two terms divisible by 5
(the second by hypothesis)
and hence also divisible by 5
Since the result is true for n = 0 (allow n = 5) &
true for n = 5k true for n = 5(k + 1)
it follows that the result is true for all non-
negative (allow “positive”) integers n | B1
B1
M1
A 1
E1 | 1.1a
2.1
3.1a
2 . 5
2.4 | Allow F = 5 as a baseline case
5
Use of (i)’s result
Only given if all 4 other marks
earned | E0 for those who fail to
distinguish between “n” and
“5n” in their explanation
[5]
Alt. Consider {F } modulo 5:
n
F = 0, F = 1 F = 1, F = 2, F = 3, F = 0,
0 1 2 3 4 5
F = 3, F = 3, F = 1, F = 4, F = 0,
6 7 8 9 10
F = 4, F = 4, F = 3, F = 2, F = 0,
11 12 13 14 15
F = 2, F = 2, F = 4, F = 1, F = 0, F = 1
16 17 18 19 20 21
Since {F } is given by a second-order, linear,
n
homogeneous r.r. and F = F = 0, and
0 20
F = F = 1, it follows that the sequence mod 5
1 21
is periodic with period 20
As F , F , F and F are all 0 (mod 5) and the
0 5 10 15
sequence repeats every 20 terms, it follows that
F 0 (mod 5) for all integers n = 0, 1, 2, …
5n | Note that there are only
5P = 5 × 4 = 20
2
pairs of the five possible residues
mod 5; thus the maximum period of
the sequence{F mod 5} is 20.
n
6 The Fibonacci sequence $\left\{ F _ { n } \right\}$ is defined by $F _ { 0 } = 0 , F _ { 1 } = 1$ and $F _ { n } = F _ { n - 1 } + F _ { n - 2 }$ for all $n \geqslant 2$.\\
(i) Show that $F _ { n + 5 } = 5 F _ { n + 1 } + 3 F _ { n }$\\
(ii) Prove that $F _ { n }$ is a multiple of 5 when $n$ is a multiple of 5 .
\hfill \mbox{\textit{OCR Further Additional Pure AS 2018 Q6 [8]}}