Question
The Fibonacci sequence can be described by the recurrence relation \({f_{n + 2}} = {f_{n + 1}} + {f_n}\) where \({f_0} = 0,\,{f_1} = 1\).
a.Write down the auxiliary equation and use it to find an expression for \({f_n}\) in terms of \(n\).[7]
b.It is known that \({\alpha ^2} = \alpha + 1\) where \(\alpha = \frac{{1 + \sqrt 5 }}{2}\).
For integers \(n\) ≥ 3, use strong induction on the recurrence relation \({f_{n + 2}} = {f_{n + 1}} + {f_n}\) to prove that \({f_n} > {\alpha ^{n – 2}}\).[8]
▶️Answer/Explanation
Markscheme
attempt to find the auxiliary equation (\({\lambda ^2} – \lambda – 1 = 0\)) M1
\(\lambda = \frac{{1 \pm \sqrt 5 }}{2}\) (A1)
the general solution is \({f_n} = A{\left( {\frac{{1 + \sqrt 5 }}{2}} \right)^n} + B{\left( {\frac{{1 – \sqrt 5 }}{2}} \right)^n}\) (M1)
imposing initial conditions (substituting \(n\) = 0,1) M1
A + B = 0 and \(A\left( {\frac{{1 + \sqrt 5 }}{2}} \right) + B\left( {\frac{{1 – \sqrt 5 }}{2}} \right) = 1\) A1
\(A = \frac{1}{{\sqrt 5 }},\,\,B = – \frac{1}{{\sqrt 5 }}\) A1
\({f_n} = \frac{1}{{\sqrt 5 }}{\left( {\frac{{1 + \sqrt 5 }}{2}} \right)^n} – \frac{1}{{\sqrt 5 }}{\left( {\frac{{1 – \sqrt 5 }}{2}} \right)^n}\) A1
Note: Condone use of decimal numbers rather than exact answers.
[7 marks]
let P(\(n\)) be \({f_n} > {\alpha ^{n – 2}}\) for integers \(n\) ≥ 3
consideration of two consecutive values of \(f\) R1
\({f_3} = 2\) and \({\alpha ^{3 – 2}} = \frac{{1 + \sqrt 5 }}{2}\left( {1.618 \ldots } \right) \Rightarrow {\text{P}}\left( 3 \right)\) is true A1
\({f_4} = 3\) and \({\alpha ^{4 – 2}} = \frac{{3 + \sqrt 5 }}{2}\left( {2.618 \ldots } \right) \Rightarrow {\text{P}}\left( 4 \right)\) is true A1
Note: Do not award A marks for values of \(n\) other than \(n\) = 3 and \(n\) = 4.
(for \(k\) ≥ 4), assume that P(\(k\)) and P(\(k\) − 1) are true M1
required to prove that P(\(k\) + 1) is true
Note: Accept equivalent notation. Needs to start with 2 general consecutive integers and then prove for the next integer. This will affect the powers of the alphas.
\({f_{k + 1}} = {f_k} + {f_{k – 1}}\) (and \({f_k} > {\alpha ^{k – 2}},\,{f_{k – 1}} > {\alpha ^{k – 3}}\)) M1
\({f_{k + 1}} > {\alpha ^{k – 2}} + {\alpha ^{k – 3}} = {\alpha ^{k – 3}}\left( {\alpha + 1} \right)\) A1
\( = {\alpha ^{k – 3}}{\alpha ^2} = {\alpha ^{k – 1}} = {\alpha ^{\left( {k + 1} \right) – 2}}\) A1
as P(3) and P(4) are true, and P(\(k\)) , P(\(k\) − 1) true ⇒ P(\(k\) + 1) true then P(\(k\)) is true for \(k\) ≥ 3 by strong induction R1
Note: To obtain the final R1, at least five of the previous marks must have been awarded.
[8 marks]
Question
a.Use the pigeon-hole principle to prove that for any simple graph that has two or more vertices and in which every vertex is connected to at least one other vertex, there must be at least two vertices with the same degree.[4]
b.Seventeen people attend a meeting.
Each person shakes hands with at least one other person and no-one shakes hands with
the same person more than once. Use the result from part (a) to show that there must be at least two people who shake hands with the same number of people.[4]
c.Explain why each person cannot have shaken hands with exactly nine other people.[2]
▶️Answer/Explanation
Markscheme
let there be \(v\) vertices in the graph; because the graph is simple the degree of each vertex is \( \le v – 1\) A1
the degree of each vertex is \( \ge 1\) A1
there are therefore \(v – 1\) possible values for the degree of each vertex A1
given there are \(v\) vertices by the pigeon-hole principle there must be at least two with the same degree R1
[4 marks]
consider a graph in which the people at the meeting are represented by the vertices and two vertices are connected if the two people shake hands M1
the graph is simple as no-one shakes hands with the same person more than once (nor can someone shake hands with themselves) A1
every vertex is connected to at least one other vertex as everyone shakes at least one hand A1
the degree of each vertex is the number of handshakes so by the proof above there must be at least two who shake the same number of hands R1
Note: Accept answers starting afresh rather than quoting part (a).
[4 marks]
(the handshaking lemma tells us that) the sum of the degrees of the vertices must be an even number A1
the degree of each vertex would be \(9\) and \(9 \times 17\) is an odd number (giving a contradiction) A1
[2 marks]
Total [10 marks]
Question
a.Consider the integers \(a = 871\) and \(b= 1157\), given in base \(10\).
(i) Express \(a\) and \(b\) in base \(13\).
(ii) Hence show that \({\text{gcd}}(a,{\text{ }}b) = 13\).[7]
b.A list \(L\) contains \(n+ 1\) distinct positive integers. Prove that at least two members of \(L\)leave the same remainder on division by \(n\).[4]
Consider the simultaneous equations
\(4x + y + 5z = a\)
\(2x + z = b\)
\(3x + 2y + 4z = c\)
where \(x,{\text{ }}y,{\text{ }}z \in \mathbb{Z}\).
(i) Show that 7 divides \(2a + b – c\).
(ii) Given that a = 3, b = 0 and c = −1, find the solution to the system of equations modulo 2.
Consider the set \(P\) of numbers of the form \({n^2} – n + 41,{\text{ }}n \in \mathbb{N}\).
(i) Prove that all elements of P are odd.
(ii) List the first six elements of P for n = 0, 1, 2, 3, 4, 5.
(iii) Show that not all elements of P are prime.
▶️Answer/Explanation
Markscheme
(i) METHOD 1
using a relevant list of powers of 13: (1), 13, 169, (2197) M1
\(871 = 5 \times {13^2} + 2 \times 13\) A1
\(871 = {520_{13}}\) A1
\(1157 = 6 \times {13^2} + 11 \times 13\) A1
\(1157 = 6{\text{B}}{{\text{0}}_{13}}\) A1
METHOD 2
attempted repeated division by 13 M1
\(871 \div 13 = 67;{\text{ }}67 \div 13 = 5{\text{rem}}2\) A1
\(871 = {520_{13}}\) A1
\(1157 \div 13 = 89;{\text{ }}89 \div 13 = 6{\text{rem11}}\) A1
\(1157 = 6{\text{B}}{{\text{0}}_{13}}\) A1
Note: Allow (11) for B only if brackets or equivalent are present.
(ii) \(871 = 13 \times 67;{\text{ }}1157 = 13 \times 89\) (M1)
67 and 89 are primes (base 10) or they are co-prime A1
So \(\gcd (871,{\text{ }}1157) = 13\) AG
Note: Must be done by hence not Euclid’s algorithm on 871 and 1157.
[7 marks]
let K be the set of possible remainders on division by n (M1)
then \(K = \{ {\text{0, 1, 2, }} \ldots n – 1\} \) has n members A1
because \(n < n + 1{\text{ }}\left( { = n(L)} \right)\) A1
by the pigeon-hole principle (appearing anywhere and not necessarily mentioned by name as long as is explained) R1
at least two members of L correspond to one member of K AG
[4 marks]
(i) form the appropriate linear combination of the equations: (M1)
\(2a + b – c = 7x + 7z\) A1
\( = 7(x + z)\) R1
so 7 divides \(2a + b – c\) AG
(ii) modulo 2, the equations become M1
\(y + z = 1\)
\(z = 0\) A1
\(x = 1\)
solution: (1, 1, 0) A1
Note: Award full mark to use of GDC (or done manually) to solve the system giving \(x = – 1,{\text{ }}y = – 3,{\text{ }}z = 2\) and then converting mod 2.
[6 marks]
(i) separate consideration of even and odd n M1
\({\text{eve}}{{\text{n}}^2} – {\text{even}} + {\text{odd is odd}}\) A1
\({\text{od}}{{\text{d}}^2} – {\text{odd}} + {\text{odd is odd}}\) A1
all elements of P are odd AG
Note: Allow other methods eg, \({n^2} – n = n(n – 1)\) which must be even.
(ii) the list is [41, 41, 43, 47, 53, 61] A1
(iii) \({41^2} – 41 + 41 = {41^2}\) divisible by 41 A1
but is not a prime R1
the statement is disproved (by counterexample) AG
[6 marks]
Examiners report
[N/A]
[N/A]
[N/A]
[N/A]