Hello, I would like to get help with the following algorithm, thank you in advance.

For the problem, provide the following: 1) A description of your algorithm in pseudo-code (well written sentences/steps are fine), 2) Proof of correctness, and 3) analysis of run time.

2. Fibonacci Fun: Use induction to prove (a), and then use this fact to design a O(log n) time algorithm for finding the nth Fibonacci number (b). F(n+1) F(n) a. Let A=( F(n) F(n-1) where F number. b. Design an O(log n) time algorithm to compute the nth Fibonacci number