8.01e Fibonacci: and related sequences (e.g. Lucas numbers)

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\).

7. Martina decides to open a bank account to help her to save for a holiday. Each month she puts \(\pounds \mathrm { k }\) into the account and allows herself to spend one quarter of what was in the account at the end of the previous month. Let \(u _ { n }\) (where \(\mathrm { n } \geqslant 1\) ) represent the amount in the account at the end of month n .
Martina has \(\pounds \mathrm {~K}\) in the account at the end of the first month.

1. By setting up a first order recurrence relation for \(u _ { n + 1 }\) in terms of \(u _ { n }\), determine an expression for \(u _ { n }\) in terms of n and k At the end of the 8th month, Martina needs to have at least \(\pounds 1750\) in the account to pay for her holiday.
2. Determine, to the nearest penny, the minimum amount of money that Martina should put into the account each month.

4 The first five terms of the Fibonacci sequence, \(\left\{ \mathrm { F } _ { \mathrm { n } } \right\}\), where \(n \geqslant 1\), are \(F _ { 1 } = 1 , F _ { 2 } = 1 , F _ { 3 } = 2 , F _ { 4 } = 3\) and \(F _ { 5 } = 5\).

1. Use the recurrence definition of the Fibonacci sequence, \(\mathrm { F } _ { \mathrm { n } + 1 } = \mathrm { F } _ { \mathrm { n } } + \mathrm { F } _ { \mathrm { n } - 1 }\), to express \(\mathrm { F } _ { \mathrm { n } + 4 }\) in terms of \(\mathrm { F } _ { \mathrm { n } }\) and \(\mathrm { F } _ { \mathrm { n } - 1 }\).
2. Hence prove by induction that \(\mathrm { F } _ { \mathrm { n } }\) is a multiple of 3 when \(n\) is a multiple of 4 .

3 For positive integers \(n\), the sequence of Fibonacci numbers, \(\left\{ \mathrm { F } _ { \mathrm { n } } \right\}\), starts with the terms \(F _ { 1 } = 1 , F _ { 2 } = 1 , F _ { 3 } = 2 , \ldots\) and is given by the recurrence relation \(\mathrm { F } _ { \mathrm { n } } = \mathrm { F } _ { \mathrm { n } - 1 } + \mathrm { F } _ { \mathrm { n } - 2 } ( \mathrm { n } \geqslant 3 )\).

1. Show that \(\mathrm { F } _ { 3 \mathrm { k } + 3 } = 2 \mathrm {~F} _ { 3 \mathrm { k } + 1 } + \mathrm { F } _ { 3 \mathrm { k } }\), where \(k\) is a positive integer.
2. Prove by induction that \(\mathrm { F } _ { 3 n }\) is even for all positive integers \(n\).

11

1. The sequence of Fibonacci Numbers \(\left\{ F _ { n } \right\}\) is given by $$F _ { 1 } = 1 , \quad F _ { 2 } = 1 \quad \text { and } \quad F _ { n + 1 } = F _ { n } + F _ { n - 1 } \text { for } n \geqslant 2 .$$ Write down the values of \(F _ { 3 }\) to \(F _ { 6 }\).
2. The sequence of functions \(\left\{ \mathrm { p } _ { n } ( x ) \right\}\) is given by $$\mathrm { p } _ { 1 } ( x ) = x + 1 \quad \text { and } \quad \mathrm { p } _ { n + 1 } ( x ) = 1 + \frac { 1 } { \mathrm { p } _ { n } ( x ) } \text { for } n \geqslant 1$$
   1. Find \(\mathrm { p } _ { 2 } ( x )\) and \(\mathrm { p } _ { 3 } ( x )\), giving each answer as a single algebraic fraction, and show that \(\mathrm { p } _ { 4 } ( x ) = \frac { 3 x + 5 } { 2 x + 3 }\).
   2. Conjecture an expression for \(\mathrm { p } _ { n } ( x )\) as a single algebraic fraction involving Fibonacci numbers, and prove it by induction for all integers \(n \geqslant 2\).