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]
Examiners report
[N/A]
[N/A]
Question
a.The sequence \(\{ {u_n}\} \) , \(n \in {\mathbb{Z}^ + }\) , satisfies the recurrence relation \({u_{n + 2}} = 5{u_{n + 1}} – 6{u_n}\) .
Given that \({u_1} = {u_2} = 3\) , obtain an expression for \({u_n}\) in terms of n .[6]
b.The sequence \(\{ {v_n}\} \) , \(n \in {\mathbb{Z}^ + }\) , satisfies the recurrence relation \({v_{n + 2}} = 4{v_{n + 1}} – 4{v_n}\) .
Given that \({v_1} = 2\) and \({v_2} = 12\) , use the principle of strong mathematical induction to show that \({v_n} = {2^n}(2n – 1)\) .[8]
▶️Answer/Explanation
Markscheme
the auxiliary equation is
\({m^2} – 5m + 6 = 0\) M1
giving \(m = 2,{\text{ 3}}\) A1
the general solution is
\({u_n} = A \times {2^n} + B \times {3^n}\) A1
substituting n = 1, 2
\(2A + 3B = 3\) M1
\(4A + 9B = 3\) A1
the solution is A = 3, B = –1 giving \({u_n} = 3 \times {2^n} – {3^n}\) A1
[6 marks]
we first prove that \({v_n} = {2^n}(2n – 1)\) for n = 1, 2 M1
for n = 1, it gives \(2 \times 1 = 2\) which is correct
for n = 2 , it gives \(4 \times 3 = 12\) which is correct A1
we now assume that the result is true for \(n \leqslant k\) M1
consider
\({v_{k + 1}} = 4{v_k} – 4{v_{k – 1}}{\text{ }}(k \geqslant 2)\) M1
\( = {4.2^k}(2k – 1) – {4.2^{k – 1}}(2k – 3)\) A1
\( = {2^{k + 1}}(4k – 2 – 2k + 3)\) A1
\( = {2^{k + 1}}\left( {2(k + 1) – 1} \right)\) A1
this proves that if the result is true for \(n \leqslant k\) then it is true for \(n \leqslant k + 1\)
since we have also proved it true for \(n \leqslant 2\) , the general result is proved by induction R1
Note: A reasonable attempt has to be made to the induction step for the final R1 to be awarded.
[8 marks]
Examiners report
[N/A]
[N/A]