Question #7 (15 points) Fibonacci numbers appear throughout mathematics. The famous Fibonacci Se- quence is defined by t

[answerhappygod]

Question 7 15 Points Fibonacci Numbers Appear Throughout Mathematics The Famous Fibonacci Se Quence Is Defined By T 1 (90.26 KiB) Viewed 24 times

Question #7 (15 points) Fibonacci numbers appear throughout mathematics. The famous Fibonacci Se- quence is defined by the following recurrence relation: F(n) = if n = 0 if n = 1 F(n − 1) + F(n − 2) if n > 2 Provide clear, concise answers to each of the following related questions. • (3 points). Prove that the recurrence is 2(n). Is it also O(n)? • (12 points). Provide a bottom-up dynamic programming solution to compute Fibonacci(n) as fast as possible.