\section*{5. For ALL APPLICANTS.}
Define the sequence, $F _ { n }$, as follows: $F _ { 1 } = 1 , F _ { 2 } = 1$, and for $n \geqslant 3$,

$$F _ { n } = F _ { n - 1 } + F _ { n - 2 } .$$

(i) [3 marks] What are the values $F _ { 3 } , F _ { 4 } , F _ { 5 }$ ?\\[0pt]
(ii) [1 mark] Using the equation (*) repeatedly, in terms of $n$, how many additions do you need to calculate $F _ { n }$ ?

We now consider sequences of 0 's and 1 's of length $n$, that do not have two consecutive 1 's. So, for $n = 5$, for example, ( $0,1,0,0,1$ ) and ( $1,0,1,0,1$ ) would be valid sequences, but ( $0,1,1,0,0$ ) would not. Let $S _ { n }$ denote the number of valid sequences of length $n$.\\[0pt]
(iii) [1 mark] What are $S _ { 1 }$ and $S _ { 2 }$ ?\\[0pt]
(iv) [3 marks] For $n \geqslant 3$, by considering the first element of the sequence of 0 's and 1's, show that $S _ { n }$ satisfies the same equation (*). Hence conclude that $S _ { n } = F _ { n + 2 }$ for all $n$.\\[0pt]
(v) [2 marks] For $n \geqslant 2$, by considering valid sequences of length $2 n - 3$ and focusing on the element in the $( n - 1 ) ^ { \text {th } }$ position, show that,

$$F _ { 2 n - 1 } = F _ { n } ^ { 2 } + F _ { n - 1 } ^ { 2 }$$

(vi) [3 marks] For $n \geqslant 2$, show that,

$$F _ { 2 n } = F _ { n } ^ { 2 } + 2 F _ { n } F _ { n - 1 }$$

(vii) [2 marks] Let $k \geqslant 3$ be an integer. By using the equations (O) and (E) repeatedly, how many arithmetic operations do you need to calculate $F _ { 2 ^ { k } }$ ? You should only count additions and multiplications needed to calculate values using the equations (O) and (E) .\\