Task 2: Christmas Lights15 Consider that you have a set of N Christmas lights, which can turn red or green. The lights are numbered from 1 to N. Initially at time step 1 they are all red. The mechanism is set such that at time t, all lights whose id is divisible by t will change color (i.e. red to green, or green to red). For example, given 6 lights, numbered 1,2,3,4,5,6 at time step 1 RRRRRR at time step 2>RGRGRG at time step 3 RGGGRR How many lights will be red at the end of N time steps ? Give a pseudocode of your algorithm and its complexity. If the algorithm complexity is O(na) then you get 5 points If the algorithm complexity is O(n) then you get 10 points If the algorithm complexity is less than O(n) then you get 15 points Task 3: Proof by Induction-10 1. Given that F(n) is the nth Fibonacci number prove that F(n)>=(3/2)n-2. Consider the numbers starting from1; i.e. F(1)=1; F(2)=1; F(3)=F(1)+F(2)=2; (5 points) 2. Given a function over positive integers, where F(O)=0; and F(n)=1+F(floor(n/2)). Then show that F(n)=1+floor(log(n)). Here floor(n/2)=(n-1)/2 if n is odd and n/2 if n is even. (5 points)