8.01g Second-order recurrence: solve with distinct, repeated, or complex roots

4

1. Solve the second-order recurrence relation \(T _ { n + 2 } + 2 T _ { n } = - 87\) given that \(T _ { 0 } = - 27\) and \(T _ { 1 } = 27\).
2. Determine the value of \(T _ { 20 }\).

6 In a national park, the number of adults of a given species is carefully monitored and controlled. The number of adults, \(n\) months after the start of this project, is \(A _ { n }\). Initially, there are 1000 adults. It is predicted that this number will have declined to 960 after one month. The first model for the number of adults is that, from one month to the next, a fixed proportion of adults is lost. In order to maintain a fixed number of adults, the park managers "top up" the numbers by adding a constant number of adults from other parks at the end of each month.

1. Use this model to express the number of adults as a first-order recurrence system. Instead, it is found that, the proportion of adults lost each month is double the predicted amount, with no change being made to the constant number of adults added each month.
2. 1. Show that the revised recurrence system for \(A _ { n }\) is \(A _ { 0 } = 1000 , A _ { n + 1 } = 0.92 A _ { n } + 40\). [1]
   2. Solve this revised recurrence system.
   3. Describe the long-term behaviour of the sequence \(\left\{ A _ { n } \right\}\) in this case. A more refined model for the number of adults uses the second-order recurrence system \(\mathrm { A } _ { \mathrm { n } + 1 } = 0.9 \mathrm {~A} _ { \mathrm { n } } - 0.1 \mathrm {~A} _ { \mathrm { n } - 1 } + 50\), for \(n \geqslant 1\), with \(A _ { 0 } = 1000\) and \(A _ { 1 } = 920\).
3. 1. Determine the long-term behaviour of the sequence \(\left\{ A _ { n } \right\}\) for this more refined model.
   2. A criticism of this more refined model is that it does not take account of the fact that the number of adults must be an integer at all times. State a modified form of the second-order recurrence relation for this more refined model that will satisfy this requirement.

8

1. Solve the second-order recurrence system \(\mathrm { H } _ { \mathrm { n } + 2 } = 5 \mathrm { H } _ { \mathrm { n } + 1 } - 4 \mathrm { H } _ { \mathrm { n } }\) with \(H _ { 0 } = 3 , H _ { 1 } = 7\) for \(n \geqslant 0\).
2. 1. Write down the quadratic residues modulo 10 .
   2. By considering the sequence \(\left\{ \mathrm { H } _ { \mathrm { n } } \right\}\) modulo 10, prove that \(\mathrm { H } _ { \mathrm { n } }\) is never a perfect square.

4

1. Solve the recurrence relation \(u _ { n + 2 } = 4 u _ { n + 1 } - 4 u _ { n }\) for \(n \geq 0\), given that \(u _ { 0 } = 1\) and \(u _ { 1 } = 1\).
2. Show that each term of the sequence \(\left\{ u _ { n } \right\}\) is an integer.

2

1. Determine the general solution of the recurrence relation \(2 u _ { n + 2 } - 7 u _ { n + 1 } + 3 u _ { n } = 0\).
2. Using your answer to part (a), determine the general solution of the recurrence relation \(2 u _ { n + 2 } - 7 u _ { n + 1 } + 3 u _ { n } = 20 n ^ { 2 } + 60 n\). In the rest of this question the sequence \(u _ { 0 } , u _ { 1 } , u _ { 2 } , \ldots\) satisfies the recurrence relation in part (b). You are given that \(u _ { 0 } = - 9\) and \(u _ { 1 } = - 12\).
3. Determine the particular solution for \(\mathrm { u } _ { \mathrm { n } }\). You are given that, as \(n\) increases, once the values of \(u _ { n }\) start to increase, then from that point onwards the sequence is an increasing sequence.
4. Use your answer to part (c) to determine, by direct calculation, the least value taken by terms in the sequence. You should show any values that you rely on in your argument.

3 A sequence is defined by the recurrence relation \(u _ { n + 2 } = 4 u _ { n + 1 } - 5 u _ { n }\) for \(n \geqslant 0\), with \(u _ { 0 } = 0\) and \(u _ { 1 } = 1\).

1. Find an exact real expression for \(u _ { n }\) in terms of \(n\) and \(\theta\), where \(\tan \theta = \frac { 1 } { 2 }\). A sequence is defined by \(v _ { n } = a ^ { \frac { 1 } { 2 } n } u _ { n }\) for \(n \geqslant 0\), where \(a\) is a positive constant.
2. In each of the following cases, describe the behaviour of \(v _ { n }\) as \(n \rightarrow \infty\).

4. A village has an expected population growth rate (birth rate minus death rate) of \(r \%\) per year. In addition, \(N\) people are expected to move into the village each year. The expected population of the village is modelled by $$u _ { n + 1 } = 1.02 u _ { n } + 50$$ where \(u _ { n }\) is the expected population of the village \(n\) years from now.

1. State
   1. the value of \(r\),
   2. the value of \(N\). Given that the population 1 year from now is expected to be 560
2. solve the recurrence relation for \(u _ { n }\)
3. Hence determine, using algebra, the number of years from now when the model predicts that the population of the village will first be greater than 3000
   (Total for Question 4 is 10 marks)
   TOTAL FOR DECISION MATHEMATICS 2 IS 40 MARKS END

1. 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,

1. 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$$
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.
3. 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]$$

5. An increasing sequence \(\left\{ u _ { n } \right\}\) for \(n \in \mathbb { N }\) is such that the difference between the \(n\)th term of \(\left\{ u _ { n } \right\}\) and the mean of the previous two terms of \(\left\{ u _ { n } \right\}\) is always 6

1. Show that, for \(n \geqslant 3\) $$2 u _ { n } - u _ { n - 1 } - u _ { n - 2 } = 12$$ Given that \(u _ { 1 } = 2\) and \(u _ { 2 } = 8\)
2. find the solution of this second order recurrence relation to obtain an expression for \(u _ { n }\) in terms of \(n\).
3. Show that as \(n \rightarrow \infty , u _ { n } \rightarrow k n\) where \(k\) is a constant to be determined. You must give reasons for your answer.

1. Sequences \(\left\{ x _ { n } \right\}\) and \(\left\{ y _ { n } \right\}\) for \(n \in \mathbb { N }\), are defined by

$$\begin{gathered} x _ { n + 1 } = 2 y _ { n } + 3 \quad \text { and } \quad y _ { n + 1 } = 3 x _ { n + 1 } - 4 x _ { n } \\ x _ { 1 } = 1 \quad \text { and } \quad y _ { 1 } = a \end{gathered}$$ where \(a\) is a constant.

1. Show that \(x _ { n + 2 } - 6 x _ { n + 1 } + 8 x _ { n } = 3\)
2. Solve the second-order recurrence relation given in (a) to obtain an expression for \(x _ { n }\) in terms of \(a\) and \(n\). Given that \(x _ { 7 } = 28225\)
3. find the value of \(a\).

5. A sequence \(\left\{ u _ { n } \right\}\), where \(\mathrm { n } \geqslant 0\), satisfies the second order recurrence relation $$u _ { n + 2 } = \frac { 1 } { 2 } \left( u _ { n + 1 } + u _ { n } \right) + 3 \text { where } u _ { 0 } = 15 \quad u _ { 1 } = 20$$

1. By considering the sequence \(\left\{ v _ { n } \right\}\), where \(u _ { n } = v _ { n } + 2 n\) for \(\mathrm { n } \geqslant 0\), determine an expression for \(u _ { n }\) as a function of n .
2. Describe the long-term behaviour of \(u _ { n }\)

5

1. (a) Solve the recurrence relation $$X _ { n + 2 } = 1.3 X _ { n + 1 } + 0.3 X _ { n } \text { for } n \geqslant 0$$ given that \(X _ { 0 } = 12\) and \(X _ { 1 } = 1\).
   (b) Show that the sequence \(\left\{ X _ { n } \right\}\) approaches a geometric sequence as \(n\) increases. The recurrence relation in part (i) models the projected annual profit for an investment company, so that \(X _ { n }\) represents the profit (in \(\pounds\) ) at the end of year \(n\).
2. (a) Determine the number of years taken for the projected profit to exceed one million pounds.
   (b) Compare your answer to part (ii)(a) with the corresponding figure given by the geometric sequence of part (i)(b).
3. (a) In a modified model, any non-integer values obtained are rounded down to the nearest integer at each step of the process. Write down the recurrence relation for this model.
   (b) Write down the recurrence relation for the model in which any non-integer values obtained are rounded up to the nearest integer at each step of the process.
   (c) Describe a situation that might arise in the implementation of part (iii)(b) that would result in an incorrect value for the next \(X _ { n }\) in the process.