Problem 1. (10 marks) Consider the following definition of Fibonacci numbers: F(n) = 0 if n=0 1 if n=1 F(n-1) + F(n 2) if n > 2 2 a. (3 marks) Give the set of all natural numbers q for which F(q) > 1.69-2. Justify briefly. (In the textbook, the set of natural numbers, denoted N, starts from 0. This is what we adopt in this course.) b. (3 marks) Does your answer to a imply the following assertion: 3c, no > 0, such that 0 no. Explain briefly. c. (4 marks) Consider the following recursive implementation of function F(n) (which differs slightly from the one given in the lecture notes). procedure fib(n) if (n = 0) then return 0 else if (n=1 or n= 2) then return 1 else return fib(n 1) + fib(n - 2) Prove by induction that the procedure fib(n) is correct