In a certain video game there is a spaceship in the middle of a screen, and a number of inter-galactic space invaders spread across the rest of the screen. The player tries to eliminate the invaders by shooting them with a laser gun attached to the spaceship. However, at the end of every 5 second period, each of the remaining invaders splits into two invaders; so if the player is not very good at shooting, the screen is eventually filled with invaders. Let In, for n > 1, denote the number of invaders on the screen at the beginning of the nth time period, and let A denote the number of invaders on the screen at the start of the game. (So I1 = A.)

(a) Draw a time-line representing the problem and write down a recurrence relation for In if the player never eliminates any invader. (b) How long does it take before there are over 1 000 000 invaders on the screen if A = 3? Now suppose that the player is able to eliminate invaders, and becomes more skillful as the game progresses. In fact, in the nth period the player can eliminate as many as 2n invaders. (c) Draw a time-line and write down the recursive formula for In in this case. (d) Find, by trial and error, the smallest value of A which leads to the screen eventually being filled by invaders (i.e. over 1 000 000). (e) Repeat parts (c) and (d) if in the nth period the player is able to eliminate n 2 invaders.