Modelling with Recurrence Relations

5 Every day, a security firm transports a large sum of money from one bank to another. There are three possible routes \(A , B\) and \(C\). The route to be used is decided just before the journey begins, by a computer programmed as follows. On the first day, each of the three routes is equally likely to be used.
If route \(A\) was used on the previous day, route \(A\), \(B\) or \(C\) will be used, with probabilities \(0.1,0.4,0.5\) respectively.
If route \(B\) was used on the previous day, route \(A , B\) or \(C\) will be used, with probabilities \(0.7,0.2,0.1\) respectively.
If route \(C\) was used on the previous day, route \(A , B\) or \(C\) will be used, with probabilities \(0.1,0.6,0.3\) respectively. The situation is modelled as a Markov chain with three states.

1. Write down the transition matrix \(\mathbf { P }\).
2. Find the probability that route \(B\) is used on the 7th day.
3. Find the probability that the same route is used on the 7th and 8th days.
4. Find the probability that the route used on the 10th day is the same as that used on the 7th day.
5. Given that \(\mathbf { P } ^ { n } \rightarrow \mathbf { Q }\) as \(n \rightarrow \infty\), find the matrix \(\mathbf { Q }\) (give the elements to 4 decimal places). Interpret the probabilities which occur in the matrix \(\mathbf { Q }\). The computer program is now to be changed, so that the long-run probabilities for routes \(A , B\) and \(C\) will become \(0.4,0.2\) and 0.4 respectively. The transition probabilities after routes \(A\) and \(B\) remain the same as before.
6. Find the new transition probabilities after route \(C\).
7. A long time after the change of program, a day is chosen at random. Find the probability that the route used on that day is the same as on the previous day. \footnotetext{Permission to reproduce items where third-party owned material protected by copyright is included has been sought and cleared where possible. Every reasonable effort has been made by the publisher (OCR) to trace copyright holders, but if any items requiring clearance have unwittingly been included, the publisher will be pleased to make amends at the earliest possible opportunity. OCR is part of the Cambridge Assessment Group. Cambridge Assessment is the brand name of University of Cambridge Local Examinations Syndicate (UCLES), which is itself a department of the University of Cambridge. }

5 A computer is programmed to generate a sequence of letters. The process is represented by a Markov chain with four states, as follows. The first letter is \(A , B , C\) or \(D\), with probabilities \(0.4,0.3,0.2\) and 0.1 respectively.
After \(A\), the next letter is either \(C\) or \(D\), with probabilities 0.8 and 0.2 respectively.
After \(B\), the next letter is either \(C\) or \(D\), with probabilities 0.1 and 0.9 respectively.
After \(C\), the next letter is either \(A\) or \(B\), with probabilities 0.4 and 0.6 respectively.
After \(D\), the next letter is either \(A\) or \(B\), with probabilities 0.3 and 0.7 respectively.

1. Write down the transition matrix \(\mathbf { P }\).
2. Use your calculator to find \(\mathbf { P } ^ { 4 }\) and \(\mathbf { P } ^ { 7 }\). (Give elements correct to 4 decimal places.)
3. Find the probability that the 8th letter is \(C\).
4. Find the probability that the 12th letter is the same as the 8th letter.
5. By investigating the behaviour of \(\mathbf { P } ^ { n }\) when \(n\) is large, find the probability that the ( \(n + 1\) )th letter is \(A\) when
   (A) \(n\) is a large even number,
   (B) \(n\) is a large odd number. The program is now changed. The initial probabilities and the transition probabilities are the same as before, except for the following. After \(D\), the next letter is \(A , B\) or \(D\), with probabilities \(0.3,0.6\) and 0.1 respectively.
6. Write down the new transition matrix \(\mathbf { Q }\).
7. Verify that \(\mathbf { Q } ^ { n }\) approaches a limit as \(n\) becomes large, and hence write down the equilibrium probabilities for \(A , B , C\) and \(D\).
8. When \(n\) is large, find the probability that the \(( n + 1 )\) th, \(( n + 2 )\) th and \(( n + 3 )\) th letters are DDD.

7 In a conservation project, a batch of 100000 tadpoles which have just hatched from eggs is introduced into an environment which has no frog population. Previous research suggests that for every 1 million tadpoles hatched only 3550 will live to maturity at 12 weeks, when they become adult frogs. It is assumed that the steady decline in the population of tadpoles, from all causes, can be explained by a weekly death-rate factor, \(r\), which is constant across each week of this twelve-week period. Let \(\mathrm { T } _ { \mathrm { k } }\) denote the total number of tadpoles alive at the end of \(k\) weeks after the start of this project.

1. 1. Explain why a recurrence system for \(\mathrm { T } _ { \mathrm { k } }\) is given by \(T _ { 0 } = 100000\) and \(\mathrm { T } _ { \mathrm { k } + 1 } = ( 1 - \mathrm { r } ) \mathrm { T } _ { \mathrm { k } }\) for \(0 \leqslant k \leqslant 12\).
   2. Show that \(r = 0.375\), correct to 3 significant figures. The proportion of females within each batch of tadpoles is \(p\), where \(0 < p < 1\). In a simple model of the frog population the following assumptions are made.
      • The death rate factor for adult frogs is also \(r\) and is the same for males and females.
2. The frog population will survive provided there are at least thirty female frogs alive sixteen weeks after the start of this project.
3. 1. Find the smallest value of \(p\) for which the frog population will survive according to the model.
   2. Write down one assumption that has been made in order to obtain this result.
Each surviving female will then lay a batch of eggs from which 2500 tadpoles are hatched.
4. By considering the total number of tadpoles hatched, give one criticism of the assumption that the frog population will survive provided there are at least thirty female frogs alive sixteen weeks after the start of this project. \section*{END OF QUESTION PAPER}

5 Let \(\mathrm { f } ( x , y ) = x ^ { 3 } + y ^ { 3 } - 2 x y + 1\). The surface \(S\) has equation \(z = \mathrm { f } ( x , y )\).

1. (a) Find \(f _ { x }\).
   (b) Find \(\mathrm { f } _ { y }\).
   (c) Show that \(S\) has a stationary point at ( \(0,0,1\) ).
   (d) Find the coordinates of the second stationary point of \(S\).
2. The section \(z = \mathrm { f } ( a , y )\), where \(a\) is a constant, has exactly one stationary point. Determine the equation of the section. A customer takes out a loan of \(\pounds P\) from a bank at an annual interest rate of \(4.9 \%\). Interest is charged monthly at an equivalent monthly interest rate. This interest is added to the outstanding amount of the loan at the end of each month, and then the customer makes a fixed monthly payment of \(\pounds M\) in order to reduce the outstanding amount of the loan. Let \(L _ { n }\) denote the outstanding amount of the loan at the end of month \(n\) after the fixed payment has been made, with \(L _ { 0 } = P\).
3. Explain how the outstanding amount of the loan from one month to the next is modelled by the recurrence relation $$L _ { n + 1 } = 1.004 L _ { n } - M$$ with \(L _ { 0 } = P , n \geq 0\).
4. Solve, in terms of \(n , M\) and \(P\), the first order recurrence relation given in part (i).
5. The loan amount is \(\pounds 100000\) and will be fully repaid after 10 years. Find, to the nearest pound, the value of the monthly repayment.
6. The bank's procedures only allow for calculations using integer amounts of pounds. When each monthly amount of the outstanding \(\operatorname { debt } \left( L _ { n } \right)\) is calculated it is always rounded up to the nearest pound before the monthly repayment ( \(M\) ) is subtracted.
   Rewrite (*) to take this into account.
7. Let \(N = 10 a + b\) and \(M = a - 5 b\) where \(a\) and \(b\) are integers such that \(a \geq 1\) and \(0 \leq b \leq 9\). \(N\) is to be tested for divisibility by 17 .
   (a) Prove that \(17 \mid N\) if and only if \(17 \mid M\).
   (b) Demonstrate step-by-step how an algorithm based on these forms can be used to show that \(17 \mid 4097\).
8. (a) Show that, for \(n \geq 2\), any number of the form \(1001 _ { n }\) is composite.
   (b) Given that \(n\) is a positive even number, provide a counter-example to show that the statement "any number of the form \(10001 _ { n }\) is prime" is false. \section*{END OF QUESTION PAPER} OCR is committed to seeking permission to reproduce all third-party content that it uses in the assessment materials. OCR has attempted to identify and contact all copyright holders whose work is used in this paper. To avoid the issue of disclosure of answer-related information to candidates, all copyright acknowledgements are reproduced in the OCR Copyright Acknowledgements booklet. This is produced for each series of examinations and is freely available to download from our public website (\href{http://www.ocr.org.uk}{www.ocr.org.uk}) after the live examination series. If OCR has unwittingly failed to correctly acknowledge or clear any third-party content in this assessment material, OCR will be happy to correct its mistake at the earliest possible opportunity.
   For queries or further information please contact the Copyright Team, First Floor, 9 Hills Road, Cambridge CB2 1GE.
   OCR is part of the Cambridge Assessment Group; Cambridge Assessment is the brand name of University of Cambridge Local Examinations Syndicate (UCLES), which is itself a department of the University of Cambridge.

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 .

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?

5 A financial institution models the repayment of a loan to a client in the following way.

• An amount, \(\pounds C\), is loaned to the client at the start of the repayment period.
• The amount owed \(n\) years after the start of the repayment period is \(\pounds L _ { n }\), so that \(L _ { 0 } = C\).
• At the end of each year, interest of \(\alpha \% ( \alpha > 0 )\) of the amount owed at the start of that year is added to the amount owed.
• Immediately after interest has been added to the amount owed a repayment of \(\pounds R\) is made by the client.
• Once \(L _ { n }\) becomes negative the repayment is finished and the overpayment is refunded to the client.
  1. Show that during the repayment period, \(L _ { n + 1 } = a L _ { n } + b\), giving \(a\) and \(b\) in terms of \(\alpha\) and \(R\).
  2. Find the solution of the recurrence relation \(L _ { n + 1 } = a L _ { n } + b\) with \(L _ { 0 } = C\), giving your solution in terms of \(a , b , C\) and \(n\).
  3. Deduce from parts (a) and (b) that, for the repayment scheme to terminate, \(R > \frac { \alpha C } { 100 }\).

A client takes out a \(\pounds 30000\) loan at \(8 \%\) interest and agrees to repay \(\pounds 3000\) at the end of each year.

1. Use an algebraic method to find the number of years it will take for the loan to be repaid.
2. Taking into account the refund of overpayment, find the total amount that the client repays over the lifetime of the loan.

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 person takes a course of a particular vitamin.

Before the course there was none of the vitamin in the person's body.
During the course, vitamin tablets are taken at the same time each day.
Initially two tablets are taken and on each following day only one tablet is taken.
Each tablet contains 10 mg of the vitamin.
Between doses the amount of the vitamin in the person's body decreases naturally by 60\% Let \(u _ { n } \mathrm { mg }\) be the amount of the vitamin in the person's body immediately after a tablet is taken, \(n\) days after the initial two tablets were taken.

1. Explain why \(u _ { n }\) satisfies the recurrence relation $$u _ { 0 } = 20 \quad u _ { n + 1 } = 0.4 u _ { n } + 10$$ The general solution to this recurrence relation has the form \(u _ { n } = a ( 0.4 ) ^ { n } + b\)
2. Determine the value of \(a\) and the value of \(b\). The course is only effective if the amount of the vitamin in the person's body remains above 6 mg at all times throughout the course.
3. Determine whether this course of the vitamin will be effective for this person, giving a reason for your answer.