Write down the auxiliary equation and use it to find an expression for ${f_n}$ in terms of $n$.

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}}$.

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]