| Date | November 2016 | Marks available | 5 | Reference code | 16N.3dm.hl.TZ0.3 |
| Level | HL only | Paper | Paper 3 Discrete mathematics | Time zone | TZ0 |
| Command term | Hence and Write down | Question number | 3 | Adapted from | N/A |
Question
In a computer game, Fibi, a magic dragon, is climbing a very large staircase. The steps are labelled 0, 1, 2, 3 … .
She starts on step 0. If Fibi is on a particular step then she can either jump up one step or fly up two steps. Let \({u_n}\) represent the number of different ways that Fibi can get to step \(n\). When counting the number of different ways, the order of Fibi’s moves matters, for example jump, fly, jump is considered different to jump, jump, fly. Let \({u_0} = 1\).
Find the values of \({u_1},{\text{ }}{u_2},{\text{ }}{u_3}\).
Show that \({u_{n + 2}} = {u_{n + 1}} + {u_n}\).
(i) Write down the auxiliary equation for this recurrence relation.
(ii) Hence find the solution to this recurrence relation, giving your answer in the form \({u_n} = A{\alpha ^n} + B{\beta ^n}\) where \(\alpha \) and \(\beta \) are to be determined exactly in surd form and \(\alpha > \beta \). The constants \(A\) and \(B\) do not have to be found at this stage.
(i) Given that \(A = \frac{1}{{\sqrt 5 }}\left( {\frac{{1 + \sqrt 5 }}{2}} \right)\), use the value of \({u_0}\) to determine \(B\).
(ii) Hence find the explicit formula for \({u_n}\).
Find the value of \({u_{20}}\).
Find the smallest value of \(n\) for which \({u_n} > 100\,000\).
Markscheme
\({u_1} = 1,{\text{ }}{u_2} = 2,{\text{ }}{u_3} = 3\) A1A1A1
[3 marks]
to get to step \(n + 2\) she can either fly from step \(n\) or jump from step \(n + 1\) R2
so \({u_{n + 2}} = {u_{n + 1}} + {u_n}\) AG
[2 marks]
(i) auxiliary equation \({\lambda ^2} - \lambda - 1 = 0\) M1A1
Note: Award M1 for attempting to write down a relevant quadratic.
(ii) \(\lambda = \frac{{1 \pm \sqrt {1 + 4} }}{2}\) M1A1
\({u_n} = A{\left( {\frac{{1 + \sqrt 5 }}{2}} \right)^n} + B{\left( {\frac{{1 - \sqrt 5 }}{2}} \right)^n}\) A1
[5 marks]
(i) \({u_0} = 1\) implies \(A + B = 1\). So \(B = - \frac{1}{{\sqrt 5 }}\left( {\frac{{1 - \sqrt 5 }}{2}} \right)\) M1A1
(ii) \({u_n} = \frac{1}{{\sqrt 5 }}{\left( {\frac{{1 + \sqrt 5 }}{2}} \right)^{n + 1}} - \frac{1}{{\sqrt 5 }}{\left( {\frac{{1 - \sqrt 5 }}{2}} \right)^{n + 1}}\) A1
Note: Accept equivalent expressions in parts (i) and (ii).
[3 marks]
\({u_{20}} = 10946\) A1
[1 mark]
using table, smallest value for \(n\) is 25 (gives 121393) (M1)A1
Note: Accept other methods, eg, logs on the dominant term.
[2 marks]
