a. (6) The Fibonacci sequence is defined by Fo= 0, F = 1, and, for all n > 2, Fn = Fn-1+ Fn-2- Prove that Fn O(2"), without using part (b). b. (6) Let An C {0, 1}" be the set of binary strings of length n with no consecutive 0's that also ends with 1. For example, the following strings are in A6: 101101, 010111, 111111. But the following strings are not in A6: 001101, 101110, 011001. Prove that if n 1 then |An| = Fn+1. c. (4) Explain why, knowing (b), part (a) is obvious. d. (4) Prove by induction that Fn1Fn+1 F2 = (-1).