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 byt 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 time steps ? Give a pseudocode of your algorithm and its complexity. If the algorithm complexity is O(n) 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 n' Fibonacci number prove that Fn)>=(3/2)^2. Consider the numbers starting from 1; 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(0)=0; and F(n)=1+F(floor(n/2)). Then show that F(n)=1+floor(loga(n)). Here floor(n/2)=(n-12 if n is odd and n/2 if n is even (5 points)