- A staircase has \(n\) steps. A tourist moves from the bottom (step zero) to the top (step \(n\) ). At each move up the staircase she can go up either one step or two steps, and her overall climb up the staircase is a combination of such moves.
If \(u _ { n }\) is the number of ways that the tourist can climb up a staircase with \(n\) steps,
- explain why \(u _ { n }\) satisfies the recurrence relation
$$u _ { n } = u _ { n - 1 } + u _ { n - 2 } , \text { with } u _ { 1 } = 1 \text { and } u _ { 2 } = 2$$
- Find the number of ways in which she can climb up a staircase when there are eight steps.
A staircase at a certain tourist attraction has 400 steps.
- Show that the number of ways in which she could climb up to the top of this staircase is given by
$$\frac { 1 } { \sqrt { 5 } } \left[ \left( \frac { 1 + \sqrt { 5 } } { 2 } \right) ^ { 401 } - \left( \frac { 1 - \sqrt { 5 } } { 2 } \right) ^ { 401 } \right]$$