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