Recall that the Fibonacci numbers are defined by the recurrence f1 = f2 = 1 and fn = fn−1 + fn−2. The next several exercises refer to this recurrence and the algorithms for computing the Fibonacci...

Recall that the Fibonacci numbers are defined by the recurrence f₁
= f₂
= 1 and fn = f_n−1
+
_fn−2. The next several exercises refer to this recurrence and the algorithms for computing the Fibonacci numbers in Figure 6.41

6.95 First, a warmup unrelated to the algorithms in Figure 6.41: prove by induction that fn ≤ 2 n

1.Prove that fibNaive(n − k) appears a total of fk+1 times in the call tree for fibNaive(n).

2. Write down and solve a recurrence for the running time of helper (and therefore fibMedium).

3. Write down and solve a recurrence for the running time of exp (and therefore fibClever).

4. The reference to “repeated squaring” in fibMatrix is precisely the same as the idea of exp. Imple