DHS Recurrence Relations (9649) (Revision Solutions)

Recurrence Relations 1 H2 Double Math (TOPICAL REVISION – SUGGESTED SOLUTION) RECURRENCE RELATIONS Question 1 [Solution] 1 (i) Solving 18 20 , 17 18p q p q= + = + => 1 ,82pq== . (ii) (Method 1) For 1p  , rewrite the RR 1nnx px q+ =+ as 1 ( ),nnx k p x k+ − = − where k R . 1 ( ) 1 nn qx p x k k q k kp k p + = − +  = − = −Then and . Let .nnu x k=− Then 1n n u pu + = is a constant and the sequence {}nu is a geometric sequence with first term 00=u x k − and common ratio p. For the sequence {}nu to be convergent, 11 p−   . (Method 2) Alternatively, limits may be used to explain the condition using the similar approach of rewriting the RR 1nnx px q+ =+ as 1 ( ),nnx k p x k+ − = − where k R . 23 1 2 3 0( ) ( ) ( ) ( ) n n n n nx k p x k p x k p x k p x k− − −− = − = − = − = = − 00lim( ) = lim ( ) = ( ) limnn nn n n x k p x k x k p → → → − − − For the sequence to be convergent, 11 p−   so that 00lim ( ) ( ) lim 0nn nn p x k x k p → → − = − = Then lim =nn xk → (iii) Since 161 qk p==− , lim = 16nn x k = → (iv) ( ) ( ) ( ) 1 2 22 21 00 1 11 ... 1 116 4 , 02 rr rr r r r r r r x px q p px q q p x q p pp x q p p p p x q p xr − −− − =+ = + + = + +  −= + + + + + = +  − = +  

Recurrence Relations 2 Question 2 [Solution] 2 “KillPest”: 10.35 500nnkk −=+ , in the long run, lim 769nn k →  “PestKill”: 10.15 650nnpp −=+ , in the long run, lim 765nn p →  Pestkill will be more effective in the long run since there will be fewer pests on the trees. Question 3 [Solution] 3 ( ) ( ) 11 1 2 1 1 1 7 15 0 7 7 8 0 7 8 0 n n n n n n n n n n n n n x x y y y yy x y x x x x ++ + + + + + + + + = + + + + =     − + + =          21 21 6 8 0 6 8 0 nn nn n n n yy y y y yy ++ ++ − + =  − + = Characteristic equation: 2 6 8 0 2 or 4 m m m m − + = == 11 ) (4 ) ) (4 ) 7)( (2 ( ( 4) 2 2 nn n nn n nn A A B Bx A y B ++ + += + = − Question 4 [Solution] 4 1 1 1 1 1 3 2 8 3 ( 1) 5 35 nn nn nn nn nn yy nyy yy nnyy uu − + − + − = − +  − = − − +  =+ Thus (3 )n nu A B=+ , where 535 2B B B= +  =− Now 1 1 2 3111 22 yu y= − = − = 1 1 5 1 5(3 ) 3 12 2 2u A A A= −  = −  = 53 2 n nu = −

Recurrence Relations 3 1 53 2 nn n y ny + = + − Question 5 [Solution] 5 114 3 (1)n n nW W I −−=+ 11 2 (2)n n nI I W −−=−  1 2 24 3( 2 ) (3)n n n nW W I W− − −= + − From (1), 2 1 234n n nI W W− − −=− Put into (3): 1 1 2 24 ( 4 ) 6n n n n nW W W W W− − − −= + − − 12 12 5 10 5 10 0 (shown) n n n n n n W W W W W W −− −− =−  − + = Auxiliary Equation: 2 5 10 0− + =  5 15 5 15 i2 2 2 −= =  1 12 1510; tan 0.65906 5r   −= = = = ( ) ( )( )210 cos 0.65906 sin 0.65906 n nW A n B n=+ 0 10 10WA=  = 1 0 0 14 3 55W W I W= +  = ( ) ( )( )55 10 10cos 0.65906 sin 0.65906 15.4919 B B =+ = ( ) ( )( )210 10cos 0.659 15.5sin 0.659 n nW n n=+ Question 6 [Solution] 6 (i) 1 2a = [ ‘1’ or ‘0’] 2 3a = [‘11’, ‘01’ or ‘10’] (ii) Case 1: string of n bits ending with a ‘1’, 1na − Case 2: string of n bits ending with a ‘0’ 2na −

Recurrence Relations 4 12 ,3n n na a a n−− = +  (iii) From GC, there are 17711 ways of constructing the string of length 20 bits. Question 7 [Solution] 7 (i) 12 3, 8aa== ( all possible cases 32 – 1 [RR] ) (ii) Considering cases for the colour of the nth tile. If nth tile is not red (i.e. gray or green), there will be 12 na − ways. If nth tile is red, we need to ensure that the (n-1)th tile must either be green or gray, there will be 22 na − ways. ( )122n n na a a −−=+ Characteristic equation: 2 2 2 0 2 132 mm m − − = = =  (1 3) (1 3)nn na A B= + + − Using 01 1, 3aa== ( ) 1 33 2 1 1 1 1 ,22 AB A B A B AB AB += + + − = −=  = + = −  1 1 1 1 (1 3) (1 ) , 122 nn nan    = + + + − −        

Recurrence Relations 5 Question 8 [Solution] 8(i) The characteristic equation for 11n n nF F F+−=+ is 2 151 0 . 2   − − =  = Hence the general solution is 1 5 1 5 .22 nn nF A B    +−=+           (ii) Since 2 1 0 0 2 1 0F F F F F F= +  = − = . Hence we have 0AB+= and 1 5 1 5 1,22AB   +− +=          which upon solving gives 1 5 A= and 1 5 B=− . Therefore 1 1 5 1 1 5 .2255 nn nF    +−=−           We can also formulate the following 2 equations and solve for A and B (but taking a longer time): 1 5 1 5 122AB   +− +=          and 22 1 5 1 5 1.22AB   +− +=          (iii) 11 00 0 00 1 1 1 5 1 1 5 3 3 2 2 55 1 1 5 1 5 6635 1 1 5 1 5 6635 111 1 5 1 535 11 66 61 35 nn n nn nn nn n nn nn F ++ ==  =  ==     +−=−               +−=−               +−=−             −=     +− − −         =    ( ) ( ) 6 5 5 5 5 6 5 5 6 5 51 1 12 5 1 .25 5 25 5 20 53 5 3 5  − −+  +−  −= = = −− 

Recurrence Relations 6 Question 9 [Solution] 9(i) Number of shrimp = previous total + new born - dead 2 1 1 1 19 2 16 39 2 16 n n n n nn x x x x xx + + + + = + − =− 21 39 2 16 n n nx x x++ =− From the recurrence relation, the auxiliary eqn is 2 39 02 16mm− + = . Since 2 3 04m −= , the general solution is 33 44 nn nx A Bn   =+        . Substitute 1 330x = and 2 360x = , we can solve to get 240A= and 200B= . 33240 20044 nn nxn    =+        (ii) 𝑥11 = 103.05 Number of shrimps = 103 000 (to nearest thousand) (iii) As n→ , 3 04 n  → and 3 04 n n → . So 0nx → . The shrimp population will die out. Question 10 [Solution] 10(i) 1 9u = (ii) Consider how an acceptable n-digit passcode can be obtained from a n-1 digits. Case I: If the n-1 digit passcode is acceptable, the nth digit cannot be 5 (since that will lead to an odd number of 5s) i.e. there are 9 digits to choose from to be the nth digit.  the number of n digits that can be formed from this case is 19 nu − . Case II: If the n-1 digit passcode is not acceptable, the the nth digit must be 5. There are 1 110n nu− −− passcodes that are not acceptable.  the number of n digits that can be formed from this case is 1 110n nu− −− . Therefore, 11 1 1 19 10 8 10nn n n n nu u u u −− − − −= + − = +

Recurrence Relations 7 (iii) ( ) 1 1 21 2 2 2 1 2 3 2 3 2 1 3 4 3 4 2 3 2 1 4 8 10 8 8 10 10 8 8 10 10 8 8 10 8 10 10 8 8 10 8 10 8 10 10 n nn nn n nn n n n n n n n n n n uu u u u u − − −− − −− − − − − − − − − − − =+ = + + = +  + = +  +  + = +  +  +  + By observation, 1 2 1 3 2 2 3 2 1 18 8 10 8 10 8 10 8 10 10n n n n n n nuu − − − − − −= +  +  + +  +  + 1 2 1 108 10 1 8 98 101 8 n n n nu − − −  −   =  + − 1 12 109 8 4 8 10 1 8 n nn nu − −−   =  −  −    12 109 8 40 8 4 8 n nn nu −−=  −  +  11 19 8 5 8 10 2 n n n nu −−=  −  +  1 14 8 10 2 nn nu −=  +  ( )1 8 102 nn nu =+ Question 11 [Solution] (a) 2 1 1 22 3 1, where 1, 2n n nu u u u u++ − + = = = Suppose the sequence nu converges, .nuL→ 2 3 1 0 1 L L L− + =  = →  the sequence diverges. (shown) (b)(i) 2 1 0 1 2 0, where 1, 2.n n nv v v v v++ − + = = = 2Auxiliary equation: 2 1 0 2 2 i cos isin 2 4 4   − + =  = =  cos sin44 n nnv A B  = +

Recurrence Relations 8 0 1 11 2 2 2 1 22 cos sin 2 cos or 2 sin4 4 4 4 4 4 n vA ABv A B B n n n nv       =  = =  + =  + =  =     = + = − +          (ii) Possible values of are 0, 1, 2.nv  Question 12 [Solution] 12 (i) 1 4n n n nu u u qu+ − = − − For the population to grow, 1 0nnuu+ − for each n + In particular, need ( )1