8.01a Recurrence relations: general sequences, closed form and recurrence

7 For each of the following sequences, write down sufficient terms of the sequence in order to be able to describe its behaviour as divergent, periodic or convergent. For any convergent sequence, state its limit.

1. \(a _ { 1 } = - 1 ; \quad a _ { k + 1 } = \frac { 4 } { a _ { k } }\)
2. \(\quad a _ { 1 } = 1 ; \quad a _ { k } = 2 - 2 \times \left( \frac { 1 } { 2 } \right) ^ { k }\)
3. \(\quad a _ { 1 } = 0 \quad a _ { k + 1 } = \left( 1 + a _ { k } \right) ^ { 2 }\).

1 Verify that \(\frac { 1 } { n ^ { 2 } } - \frac { 1 } { ( n + 1 ) ^ { 2 } } = \frac { 2 n + 1 } { n ^ { 2 } ( n + 1 ) ^ { 2 } }\). Let \(S _ { N } = \sum _ { r = 1 } ^ { N } \frac { 2 r + 1 } { r ^ { 2 } ( r + 1 ) ^ { 2 } }\). Express \(S _ { N }\) in terms of \(N\). Let \(S = \lim _ { N \rightarrow \infty } S _ { N }\). Find the least value of \(N\) such that \(S - S _ { N } < 10 ^ { - 16 }\).

4 The sequence \(\left\{ \mathrm { u } _ { \mathrm { n } } \right\}\) is defined by \(u _ { 1 } = 1\) and \(\mathrm { u } _ { \mathrm { n } + 1 } = 2 \mathrm { u } _ { \mathrm { n } } + \mathrm { n } ^ { 2 }\) for \(\mathrm { n } \geqslant 1\).
Determine \(u _ { n }\) as a function of \(n\).

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

6 The sequence \(\left\{ u _ { n } \right\}\) is such that \(u _ { 1 } = 7 , u _ { 2 } = 37 , u _ { 3 } = 337 , u _ { 4 } = 3337 , \ldots\).

1. Write down a first-order recurrence system for \(\left\{ \mathrm { u } _ { \mathrm { n } } \right\}\).
2. By solving the recurrence system of part (a), show that \(\mathrm { u } _ { \mathrm { n } } = \frac { 1 } { 3 } \left( 10 ^ { \mathrm { n } } + 11 \right)\).
3. Prove that \(\left\{ \mathrm { u } _ { \mathrm { n } } \right\}\) contains infinitely many terms which are multiples of 37 .

1 The sequence \(\left\{ u _ { n } \right\}\) is defined by \(u _ { 0 } = 2 , u _ { 1 } = 5\) and \(u _ { n } = \frac { 1 + u _ { n - 1 } } { u _ { n - 2 } }\) for \(n \geqslant 2\).
Prove that the sequence is periodic with period 5.

5 In a conservation project in a nature reserve, scientists are modelling the population of one species of animal. The initial population of the species, \(P _ { 0 }\), is 10000 . After \(n\) years, the population is \(P _ { n }\). The scientists believe that the year-on-year change in the population can be modelled by a recurrence relation of the form \(\mathrm { P } _ { \mathrm { n } + 1 } = 2 \mathrm { P } _ { \mathrm { n } } \left( 1 - \mathrm { k } \mathrm { P } _ { \mathrm { n } } \right)\) for \(n \geqslant 0\), where \(k\) is a constant.

1. The initial aim of the project is to ensure that the population remains constant. Show that this happens, according to this model, when \(k = 0.00005\).
2. After a few years, with the population still at 10000 , the scientists suggest increasing the population. One way of achieving this is by adding 50 more of these animals into the nature reserve at the end of each year. In this scenario, the recurrence system modelling the population (using \(k = 0.00005\) ) is given by \(P _ { 0 } = 10000\) and \(\mathrm { P } _ { \mathrm { n } + 1 } = 2 \mathrm { P } _ { \mathrm { n } } \left( 1 - 0.00005 \mathrm { P } _ { \mathrm { n } } \right) + 50\) for \(n \geqslant 0\).
   Use your calculator to find the long-term behaviour of \(P _ { n }\) predicted by this recurrence system.
3. However, the scientists decide not to add any animals at the end of each year. Also, further research predicts that certain factors will remove 2400 animals from the population each year.
   1. Write down a modified form of the recurrence relation given in part (b), that will model the population of these animals in the nature reserve when 2400 animals are removed each year and no additional animals are added.
   2. Use your calculator to find the behaviour of \(P _ { n }\) predicted by this modified form of the recurrence relation over the course of the next ten years.
   3. Show algebraically that this modified form of the recurrence relation also gives a constant value of \(P _ { n }\) in the long term, which should be stated.
   4. Determine what constant value should replace 0.00005 in this modified form of the recurrence relation to ensure that the value of \(P _ { n }\) remains constant at 10000 .

8 The sequence \(\left\{ u _ { n } \right\}\) of positive real numbers is defined by \(u _ { 1 } = 1\) and \(u _ { n + 1 } = \frac { 2 u _ { n } + 3 } { u _ { n } + 2 }\) for \(n \geqslant 1\).

1. Prove by induction that \(u _ { n } ^ { 2 } - 3 < 0\) for all positive integers \(n\).
2. By considering \(u _ { n + 1 } - u _ { n }\), use the result of part (a) to show that \(u _ { n + 1 } > u _ { n }\) for all positive integers \(n\). The sequence \(\left\{ u _ { n } \right\}\) has a limit for \(n \rightarrow \infty\).
3. Find the limit of the sequence \(\left\{ u _ { n } \right\}\) as \(n \rightarrow \infty\).
4. Describe as fully as possible the behaviour of the sequence \(\left\{ u _ { n } \right\}\). \section*{END OF QUESTION PAPER}

9 For each value of \(k\) the sequence of real numbers \(\left\{ u _ { n } \right\}\) is given by \(u _ { 1 } = 2\) and \(u _ { n + 1 } = \frac { k } { 6 + u _ { n } }\). For each of the following cases, either determine a value of \(k\) or prove that one does not exist.

1. \(\left\{ \mathrm { u } _ { n } \right\}\) is constant.
2. \(\left\{ \mathrm { u } _ { \mathrm { n } } \right\}\) is periodic, with period 2 .
3. \(\left\{ \mathrm { u } _ { \mathrm { n } } \right\}\) is periodic, with period 4 .

7 In order to rescue them from extinction, a particular species of ground-nesting birds is introduced into a nature reserve. The number of breeding pairs of these birds in the nature reserve, \(t\) years after their introduction, is an integer denoted by \(N _ { t }\). The initial number of breeding pairs is given by \(N _ { 0 }\). An initial discrete population model is proposed for \(N _ { t }\). $$\text { Model I: } N _ { t + 1 } = \frac { 6 } { 5 } N _ { t } \left( 1 - \frac { 1 } { 900 } N _ { t } \right)$$

1. (a) For Model I, show that the steady state values of the number of breeding pairs are 0 and 150 .
   (b) Show that \(N _ { t + 1 } - N _ { t } < 150 - N _ { t }\) when \(N _ { t }\) lies between 0 and 150 .
   (c) Hence find the long-term behaviour of the number of breeding pairs of this species of birds in the nature reserve predicted by Model I when \(N _ { 0 } \in ( 0,150 )\). An alternative discrete population model is proposed for \(N _ { t }\). $$\text { Model II: } N _ { t + 1 } = \operatorname { INT } \left( \frac { 6 } { 5 } N _ { t } \left( 1 - \frac { 1 } { 900 } N _ { t } \right) \right)$$
2. (a) Given that \(N _ { 0 } = 8\), find the value of \(N _ { 4 }\) for each of the two models.
   (b) Which of the two models gives values for \(N _ { t }\) with the more appropriate level of precision?

1 Three sequences, \(\mathrm { a } _ { \mathrm { n } } , \mathrm { b } _ { \mathrm { n } }\) and \(\mathrm { c } _ { \mathrm { n } }\), are defined for \(n \geqslant 1\) by the following recurrence relations. $$\begin{aligned} & \left( a _ { n + 1 } - 2 \right) \left( 2 - a _ { n } \right) = 3 \text { with } a _ { 1 } = 3 \\ & b _ { n + 1 } = - \frac { 1 } { 2 } b _ { n } + 3 \text { with } b _ { 1 } = 1.5 \\ & c _ { n + 1 } - \frac { c _ { n } ^ { 2 } } { n } = 1 \text { with } c _ { 1 } = 2.5 \end{aligned}$$ The output from a spreadsheet which presents the first 10 terms of \(a _ { n } , b _ { n }\) and \(c _ { n }\), is shown below. Without attempting to solve any recurrence relations, describe the apparent behaviour, including as \(n \rightarrow \infty\), of

• \(a _ { n }\)
• \(\mathrm { b } _ { \mathrm { n } }\)
• \(\mathrm { C } _ { \mathrm { n } }\)

2 A sequence is defined by the recurrence relation \(4 \mathrm { t } _ { \mathrm { n } + 1 } - \mathrm { t } _ { \mathrm { n } } = 15 \mathrm { n } + 17\) for \(\mathrm { n } \geqslant 1\), with \(t _ { 1 } = 2\).

1. Solve the recurrence relation to find the particular solution for \(\mathrm { t } _ { \mathrm { n } }\). Another sequence is defined by the recurrence relation \(( n + 1 ) u _ { n + 1 } - u _ { n } ^ { 2 } = 2 n - \frac { 1 } { n ^ { 2 } }\) for \(n \geqslant 1\), with \(u _ { 1 } = 2\).
2. 1. Explain why the recurrence relation for \(\mathrm { u } _ { \mathrm { n } }\) cannot be solved using standard techniques for non-homogeneous first order recurrence relations.
   2. Verify that the particular solution to this recurrence relation is given by \(u _ { n } = a n + \frac { b } { n }\) where \(a\) and \(b\) are constants whose values are to be determined. A third sequence is defined by \(\mathrm { v } _ { \mathrm { n } } = \frac { \mathrm { t } _ { \mathrm { n } } } { \mathrm { u } _ { \mathrm { n } } }\) for \(n \geqslant 1\).
3. Determine \(\lim _ { n \rightarrow \infty } \mathrm { v } _ { \mathrm { n } }\).

2 A sequence is defined by the recurrence relation \(t _ { n + 1 } = \frac { t _ { n } } { n + 3 }\) for \(n \geqslant 1\), with \(t _ { 1 } = 8\).
Verify that the particular solution to the recurrence relation is given by \(t _ { n } = \frac { a } { ( n + b ) ! }\) where \(a\) and \(b\) are constants whose values are to be determined.

3 A tree at the bottom of a garden needs to be reduced in height. The tree is known to increase in height by 15 centimetres each year. On the first day of every year, the height is measured and the tree is immediately trimmed by \(3 \%\) of this height. When the tree is measured, before trimming on the first day of year 1 , the height is 6 metres.
Let \(H _ { n }\) be the height of the tree immediately before trimming on the first day of year \(n\).

1. Explain, in the context of the problem, why the height of the tree may be modelled by the recurrence relation $$H _ { n + 1 } = 0.97 H _ { n } + 0.15 , \quad H _ { 1 } = 6 , \quad n \in \mathbb { Z } ^ { + }$$
2. Prove by induction that \(H _ { n } = 0.97 ^ { n - 1 } + 5 , \quad n \geqslant 1\)
3. Explain what will happen to the height of the tree immediately before trimming in the long term.
4. By what fixed percentage should the tree be trimmed each year if the height of the tree immediately before trimming is to be 4 metres in the long term?

1. On Jim's 11 th birthday his parents invest \(\pounds 1000\) for him in a savings account.

The account earns 2\% interest each year.
On each subsequent birthday, Jim's parents add another \(\pounds 500\) to this savings account.
Let \(U _ { n }\) be the amount of money that Jim has in his savings account \(n\) years after his 11th birthday, once the interest for the previous year has been paid and the \(\pounds 500\) has been added.

1. Explain, in the context of the problem, why the amount of money that Jim has in his savings account can be modelled by the recurrence relation of the form $$U _ { n } = 1.02 U _ { n - 1 } + 500 \quad U _ { 0 } = 1000 \quad n \in \mathbb { Z } ^ { + }$$
2. State an assumption that must be made for this model to be valid.
3. Solve the recurrence relation $$U _ { n } = 1.02 U _ { n - 1 } + 500 \quad U _ { 0 } = 1000 \quad n \in \mathbb { Z } ^ { + }$$ Jim hopes to be able to buy a car on his 18th birthday.
4. Use the answer to part (c) to find out whether Jim will have enough money in his savings account to buy a car that costs \(\pounds 4500\)

1. Sam borrows \(\pounds 10000\) from a bank to pay for an extension to his house.

The bank charges \(5 \%\) annual interest on the portion of the loan yet to be repaid. Immediately after the interest has been added at the end of each year and before the start of the next year, Sam pays the bank a fixed amount, \(\pounds F\). Given that \(\pounds A _ { n }\) (where \(A _ { n } \geqslant 0\) ) is the amount owed at the start of year \(n\),

1. write down an expression for \(A _ { n + 1 }\) in terms of \(A _ { n }\) and \(F\),
2. prove, by induction that, for \(n \geqslant 1\) $$A _ { n } = ( 10000 - 20 F ) 1.05 ^ { n - 1 } + 20 F$$
3. Find the smallest value of \(F\) for which Sam can repay all of the loan by the start of year 16 .

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]$$

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.

6 For real constants \(a\) and \(b\), the sequence \(U _ { 1 } , U _ { 2 } , U _ { 3 } , \ldots\) is given by $$U _ { 1 } = a \text { and } U _ { n } = \left( U _ { n - 1 } \right) ^ { 2 } - b \text { for } n \geqslant 2 .$$

1. Determine the behaviour of the sequence in the case where \(a = 1\) and \(b = 3\).
2. In the case where \(b = 6\), find the values of \(a\) for which the sequence is constant.
3. In the case where \(a = - 1\) and \(b = 8\), prove that \(U _ { n }\) is divisible by 7 for all even values of \(n\).

3 In this question you must show detailed reasoning.

1. The sequence \(\left\{ A _ { n } \right\}\) is given by \(A _ { 1 } = \sqrt { 3 }\) and \(A _ { n + 1 } = ( \sqrt { 3 } + 1 ) A _ { n }\) for \(n \geqslant 1\). Find an expression for \(A _ { n }\) in terms of \(n\).
2. The sequence \(\left\{ B _ { n } \right\}\) is given by the formula $$B _ { n } = \frac { 1 } { \sqrt { 3 } } \left( ( \sqrt { 3 } + 1 ) ^ { n } - ( \sqrt { 3 } - 1 ) ^ { n } \right) \text { for } n \geqslant 1 .$$ Explain why \(B _ { n } \rightarrow \frac { 1 } { \sqrt { 3 } } ( \sqrt { 3 } + 1 ) ^ { n }\) as \(n \rightarrow \infty\).
3. The sequence \(\left\{ C _ { n } \right\}\) converges and is defined by \(C _ { n } = \frac { A _ { n } } { B _ { n } }\) for \(n \geqslant 1\). Identify the limit of \(C n\) as \(n \rightarrow \infty\).

7 Irrational numbers can be modelled by sequences \(\left\{ u _ { n } \right\}\) of rational numbers of the form $$u _ { 0 } = 1 \text { and } u _ { n + 1 } = a + \frac { 1 } { b + u _ { n } } \text { for } n \geqslant 0 \text {, }$$ where \(a\) and \(b\) are non-negative integer constants.

1. (a) The constants \(a = 1\) and \(b = 0\) produce the irrational number \(\omega\). State the value of \(\omega\) correct to six decimal places.
   (b) By setting \(u _ { n + 1 }\) and \(u _ { n }\) equal to \(\omega\), determine the exact value of \(\omega\).
2. Use the method of part (i) (b) to find the exact value of the irrational number produced by taking \(a = 0\) and \(b = 2\).
3. Find positive integers \(a\) and \(b\) which would produce the irrational number \(2 + \sqrt { 10 }\). \section*{END OF QUESTION PAPER}

2 A sequence \(\left\{ u _ { n } \right\}\) is given by \(u _ { n + 1 } = 4 u _ { n } + 1\) for \(n \geqslant 1\) and \(u _ { 1 } = 3\).

1. Find the values of \(u _ { 2 } , u _ { 3 }\) and \(u _ { 4 }\).
2. Solve the recurrence system (*).
3. 1. Prove by induction that each term of the sequence can be written in the form \(( 10 m + 3 )\) where \(m\) is an integer.
   2. Show that no term of the sequence is a square number.

8 A sequence \(\left\{ \mathrm { u } _ { \mathrm { n } } \right\}\) is defined by the recurrence system \(u _ { 1 } = 1\) and \(\mathrm { u } _ { \mathrm { n } + 1 } = \mathrm { a } - \frac { \mathrm { a } ^ { 2 } } { 2 \mathrm { u } _ { \mathrm { n } } }\) for \(n \geqslant 1\), where \(a\) is a positive constant.
Determine with justification the behaviour of the sequence for all possible values of \(a\). \section*{END OF QUESTION PAPER}

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

Given that $$u_n = \frac{1}{n^2 - n + 1} - \frac{1}{n^2 + n + 1},$$ find \(S_N = \sum_{n=N+1}^{2N} u_n\) in terms of \(N\). [3] Find a number \(M\) such that \(S_N < 10^{-20}\) for all \(N > M\). [3]