Both questions go together, please provide/show work and share thoughts, thank you.

2. Let Fn denote the nth Fibonacci number. Let A=(1110). Show that An=(Fn+1FnFnFn1). (Hint: use induction). 3. Use the equality proven in question 2 to design an algorithm to compute the nth Fibonacci number in O(logn) time