DHS Recurrence Relations (9649) Topical Revision

Recurrence Relations 1 H2 Double Math (TOPICAL REVISION) RECURRENCE RELATIONS 1 A sequence is defined by the recurrence relation 10 , where 1 1, 20, 0, ,nnx px q p x n p q .+ = + −   =   R (i) If 1 18x = and 2 17x = , find the values of p and q. (ii) Explain, using limits or otherwise, why the condition 11 p−   is required for the sequence to be convergent. (iii) Find the limit of the sequence. (iv) Find a formula for rx in terms of r. 2 Trees are sprayed weekly with the pesticide, ‘Killpest’, whose manufacturers claim it will destroy 65% of all pests. Between the weekly sprayings, it is estimated that 500 new pests invade the trees. A new pesticide, ‘Pestkill’, comes onto the market. The manufacturers claim it will destroy 85% of existing pests but it is estimated that 650 new pests per week will invade the trees. Which pesticide will be more effective in the long term? 3 Using the substitution 1 7n n n yx y +=− where 0,ny  show that the recurrence relation 11 7 15 0n n n nx x x x++ + + + = can be expressed as 21 0,n n ny ay by+++ + = where a and b are constants to be found. Hence, find the general solution of nx in the form of f ( ) 7n − where f ( )n is an expression in terms of .n [5] [DHS et.al./Prelim 9649/2020/01/Q1] 4 The sequence of positive real numbers  ny is given by 12 3, 2yy== and 1 1 3 2 8,nn nn yy nyy − + = − +  for 2.n (i) By using the substitution 1 ,n n n yun y + =− determine a first order recurrence relation in terms of 1ny + , ny and n. [5] [DHS/Promo 9649/2021/Q5(i)]

Recurrence Relations 2 5 Terms in the sequences nW and nI are defined as follow. 11 10 for 0, 4 3 for 1,n nn nW W I n−− == + and 11 5 for 0, 2 for 1.n nn nI I W n−− == − Show that 125 10 0 for 2.n n nW W W n−−− + =  Hence find an expression for nW in terms of n. [9] [VJC Promo 9649/2021/Q5] 6 A bit is represented by a binary number i.e. 0 or 1. A string of n bits is constructed such that there are no two consecutive 0s. Let na be the number of ways to construct this string. (i) Find 1a and 2a . (ii) By considering the cases for the string ending with either a 0 or 1, find a recurrence relation for na . (iii) Find the number of ways to construct this type of string with 20 bits. 7 A walkway is laid with n slate tiles. The color of the slate tiles are either red, green or gray. The tiles are laid on the walkway such that no two red tiles are adjacent and tiles of the same color are indistinguishable. Let na be the number of ways to lay out n tiles in the walkway. (i) Find 1a and 2a . (ii) Find a 2nd order recurrence relation for na . Hence express na in terms of n. 8 The terms in the sequence 0 1 2 3, , , , F F F F satisfy the recurrence relation 11n n nF F F+−=+ for 1n . (i) Find the general solution of this recurrence relation. [2] (ii) Find an expression for nF in terms of n given that 1 1F = and 2 1F = . [2] (iii) Hence find the exact value of 1 0 3 n n n F + =  , simplifying your answer as far as possible. [4] [RI/FM/2019/MCT/Q1] 9 A marine biologist keeps a water tank of brine shrimp for her research. At the end of each week, she finds that the number of new-born shrimp is equal to half of the number of shrimp one week ago, while the number of dead shrimp in the tank is 9 16 of the number of shrimp two weeks ago. The number of shrimp (in thousands) in the tank at the end of week n is given by nx . (i) Form a recurrence relation and solve the recurrence relation, given that 1 330x = and 2 360x = . [6] (ii) Find the number of shrimp at the end of week 11, giving your answer to the nearest thousand. [1]

Recurrence Relations 3 (iii) Explain what happens to the shrimp population if the research continues indefinitely. [2] [HCI et al/FM/2018/P1/Q2] 10 A website requires numerical passcodes only using the digits 0 to 9, with repetition allowed. In addition, a passcode is considered acceptable if the passcode contains an even number of the digit 5. For example, the 7 -digit passcode 0505055 is acceptable but 0505005 is not acceptable. Let nu be the number of n-digit acceptable passcodes. (i) State the value of 1u . [1] (ii) Formulate with clear reasoning, a first order recurrence relation of the form 1 1 n nnu au b − −=+ , 2n , where , ab are constants to be determined. [3] (iii) Hence, by repeated substitution, find nu in the form ( )1 nn nu a bk=+ , k + . [4] [TJC/FM/2019/P2//Q1] 11 (a) The sequence , 1,nun  satisfies the recurrence relation 2 1 1 22 3 1, where 1, 2.n n nu u u u u++ − + = = = Without solving for ,nu prove that the sequence diverges. [2] (b) The sequence , 0,nvn  satisfies the recurrence relation 21 20n n nv v v++ − + = , where 01 1, 2vv== (i) Express nv as a single trigonometric function of n. [5] (ii) Hence, write down all possible values of the sequence. [2] [VJC/FM/2019/P2/Q3] 12 A researcher breeds fruitflies in a small jar for experimental purposes. Observations of the number of fruitflies at the end of each week suggest that the population satisfies the following recurrence relation, ( )1 24nnu q u+ = − − , where un denotes the number of fruitflies at the end of the nth week and q denotes the proportion of fruitflies that die of natural causes over the week. (i) Given that 1q , by considering un + 1 – un, show that there must initially be more than ( ) 1 41 q − − fruitflies in the jar for the population of fruitflies to grow. (ii) Suppose that there are 10 and 15 fruitflies in the jar at the end of the first and second weeks respectively. Find the value of q and calculate the number of fruitflies in the jar at the end of the 20th week, giving your answer to 1 significant figure. Comment on the practicality of your answer. (iii) Another researcher suggests using a differential equation to model the growth of the population of fruitflies instead of a recurrence relation. Should this suggestion be taken up? Explain your answer.

Recurrence Relations 4 13 The life cycle of kaka, a newly -discovered micro -organism, consists of three stages, namely nympha, iuvenis and adultus. After one day, an existing nympha kaka will mature into an iuvenis kaka, an existing iuvenis kaka will mature into an adultus kaka and adultus kaka will remain as adultus kaka. Kaka undergoes a special type of asexual reproduction. On the day when a nympha kaka matures into an iuvenis kaka, it produces one nympha kaka. On the day when an iuvenis kaka matures into an adultus kaka, it produces nine nympha kaka. On every subsequent day in its lifetime, an adultus kaka will continue to produce nine nympha kaka. Stephen accidentally comes in contact with two nympha kaka on a particular day. Let nu be the number of kaka in Stephen’s body on the nth day. (i) Formulate a recurrence relation relating nu , 1nu − and 2nu − , stating the values of 1u and 2u . [3] (ii) Find the number of kaka found in Stephen’s body on the nth day. [4] (iii) State an assumption in your workings. [1] [AJC/2016/promo/4] 14 In an interrogation procedure, a captured espionage will be given a 25 milligram dose of a truth serum every 4 hours. 15% of the truth serum present in his body is lost every hour. Let nu be the amount of the serum in his body just after the nth dose. (i) Calculate, in milligrams, the amount of truth serum remaining in his body after 4 hours and just before the second dose is administered. [1] (ii) Find a recurrence relation that nu satisfies in the form 1nnu au b+ =+ , where a and b are constants to be determined. [2] (iii) Solve the recurrence relation stated in (ii). [4] (iv) It is known that the level of serum in the body has to be continuously above 20 milligram