Quiz 2 Problem 4.[15 points] A misguided MIT student designs a self-replicating 6.270 robot The student builds one such robot every day, starting on day 0. The day after a robot is built, it constructs two copies of itself. (On all subsequent days, the robot busily searches for ping-pong balls--these are 6.270 robots, after all. )Here is what happens over the first few days Day 0. The student builds robot R1 Day 1. The student builds robot R2 Robot Ri builds robots Rs and R Day 2. The student builds Rs. Robot R2 builds Rs and Rr, robot R3 builds Rg and Rg, and robot R builds Rio and Rll Robot Ri searches for ping-pong balls ay 3. The student builds R12. Robots Rs,..., Rul build robots R13,., R26. Robots Ri R2, R3, and R4 search for ping-pong balls Let Tn be the number of robots in existence at the end of day n. Thus, To =l, Ti=4, T2=11,andT3=26 (a)How many new robots are built on day n-1? Express your answer in terms of the variables T-1, Tn-2,. and assume n>2. Solution. This is the difference between the number that existed on day n-1 and the number that existed on day n-2, which is Tn-1-Tn-2 (b) Express Tn with a recurrence equation and sufficient base cases. Do not solve the recurrence Solution. The number of robots on day n is equal to the number of robots on day n-1, plus twice the number of robots built yesterday (Tn-1-Tn-2), plus the 1 robot built by the student Therefore we have: T1=4 Tn=3Tn-1-2Tn-2+1(for n> 2)Quiz 2 6 Problem 4. [15 points] A misguided MIT student designs a self­replicating 6.270 robot. The student builds one such robot every day, starting on day 0. The day after a robot is built, it constructs two copies of itself. (On all subsequent days, the robot busily searches for ping­pong balls— these are 6.270 robots, after all.) Here is what happens over the first few days: Day 0. The student builds robot R1. Day 1. The student builds robot R2. Robot R1 builds robots R3 and R4. Day 2. The student builds R5. Robot R2 builds R6 and R7, robot R3 builds R8 and R9, and robot R4 builds R10 and R11. Robot R1 searches for ping­pong balls. Day 3. The student builds R12. Robots R5, . . . , R11 build robots R13, . . . , R26. Robots R1, R2, R3, and R4 search for ping­pong balls. Let Tn be the number of robots in existence at the end of day n. Thus, T0 = 1, T1 = 4, T2 = 11, and T3 = 26. (a) How many new robots are built on day n − 1? Express your answer in terms of the variables Tn−1, Tn−2, . . . and assume n ≥ 2. Solution. This is the difference between the number that existed on day n − 1 and the number that existed on day n − 2, which is Tn−1 − Tn−2. (b) Express Tn with a recurrence equation and sufficient base cases. Do not solve the recurrence. Solution. The number of robots on day n is equal to the number of robots on day n − 1, plus twice the number of robots built yesterday (Tn−1 − Tn−2), plus the 1 robot built by the student. Therefore, we have: T0 = 1 T1 = 4 Tn = 3Tn−1 − 2Tn−2 + 1 (for n ≥ 2)