Fibonacci and Related Sequences

6 The Fibonacci sequence \(\left\{ F _ { n } \right\}\) is defined by \(F _ { 0 } = 0 , F _ { 1 } = 1\) and \(F _ { n } = F _ { n - 1 } + F _ { n - 2 }\) for all \(n \geqslant 2\).

1. Show that \(F _ { n + 5 } = 5 F _ { n + 1 } + 3 F _ { n }\)
2. Prove that \(F _ { n }\) is a multiple of 5 when \(n\) is a multiple of 5 .

3 The sequence \(\left\{ U _ { n } \right\}\) is given by \(U _ { 1 } = 0 , U _ { 2 } = - 1\) and \(U _ { n + 2 } = U _ { n + 1 } + U _ { n } + n - 1\) for \(n \geqslant 1\).

1. List the first seven terms of this sequence. The Fibonacci sequence \(\left\{ \mathrm { F } _ { \mathrm { n } } \right\}\) is given by \(\mathrm { F } _ { 1 } = 1 , \mathrm {~F} _ { 2 } = 1\) and \(\mathrm { F } _ { \mathrm { n } + 2 } = \mathrm { F } _ { \mathrm { n } + 1 } + \mathrm { F } _ { \mathrm { n } }\) for \(n \geqslant 1\).
2. 1. By comparing the two sequences, give the relationship between \(\mathrm { U } _ { \mathrm { n } }\) and \(\mathrm { F } _ { \mathrm { n } }\).
   2. Show that the relationship found in part (b)(i) holds for all \(n \geqslant 1\).

7 Binet's formula for the \(n\)th Fibonacci number is given by \(\mathrm { F } _ { \mathrm { n } } = \frac { 1 } { \sqrt { 5 } } \left( \alpha ^ { \mathrm { n } } - \beta ^ { \mathrm { n } } \right)\) for \(n \geqslant 0\), where \(\alpha\) and \(\beta\) (with \(\alpha > 0 > \beta\) ) are the roots of \(x ^ { 2 } - x - 1 = 0\).

1. Write down the values of \(\alpha + \beta\) and \(\alpha \beta\).
2. Consider the sequence \(\left\{ \mathrm { S } _ { \mathrm { n } } \right\}\), where \(\mathrm { S } _ { \mathrm { n } } = \alpha ^ { \mathrm { n } } + \beta ^ { \mathrm { n } }\) for \(n \geqslant 0\).
   1. Determine the values of \(S _ { 2 }\) and \(S _ { 3 }\).
   2. Show that \(S _ { n + 2 } = S _ { n + 1 } + S _ { n }\) for \(n \geqslant 0\).
   3. Deduce that \(S _ { n }\) is an integer for all \(n \geqslant 0\).
3. A student models the terms of the sequence \(\left\{ \mathrm { S } _ { \mathrm { n } } \right\}\) using the formula \(\mathrm { T } _ { \mathrm { n } } = \alpha ^ { \mathrm { n } }\).
   1. Explain why this formula is unsuitable for every \(n \geqslant 1\).
   2. Considering the cases \(n\) even and \(n\) odd separately, state a modification of the formula \(\mathrm { T } _ { \mathrm { n } } = \alpha ^ { \mathrm { n } }\), other than \(\mathrm { T } _ { \mathrm { n } } = \alpha ^ { \mathrm { n } } + \beta ^ { \mathrm { n } }\), such that \(\mathrm { T } _ { \mathrm { n } } = \mathrm { S } _ { \mathrm { n } }\) for all \(n \geqslant 1\).