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]