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\).

\({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]