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]