Theorem 1 For any n E N if n > 1 then f(n; a,b) = f(n - 1; a,b) + f(n 2; a,b). Theorem 2 For any n e N, Fn = f(n;0,1). Theorem 3 For any n e N, Fn = + (6" 6m), where 4 = l5 and = 1-V5. 1. The function fib implemented the recurrence Fn. We can characterize the time taken by fib in terms of the number of additions (plusses) performed. We can write a recurrence TF(n) that computes this number as follows. Observe that there are no additions performed for the base cases. Hence TF(0) = 0 and TF(1) = 0. Also observe that the number of additions to compute Fn is one more than the number of additions to compute Fn-1 together with the number of additions to compute Fn-2. Hence TF(n) = 1 +Tf(n 1) + TF(n 2). Putting this together, we have the following recurrence. TF(0) TF(1) TF(n) = 0 0 1 + TF(n-1) + TF(n - 2) It turns out that for any n E N, TF(n) = Fn+1 - 1. Use limits together with theorem 3 to show that TF(n) (6")