3. The Fibonacci numbers F_n (n∈N) are defined by F₁ ^def 1.

F₂ ^def 1.

F_n+2 ^def F_n+1 + F_n

for all n ∈ N.

(a) Compute F7.

(b) Prove: If a > b ≥ 0 are integers such that the program Euclid

(a,

b) makes k ∈ N recursive calls, then a ≥ Fk+2 and b ≥ Fk+1 hold. (Hint: Use mathematical induction on k.)

(c) Prove: The program Euclid(F[k+1], F[k]) makes exactly k - 1 recursive calls for all k ∈ N. (Hint: Use mathematical induction on k and the recursive definition of the Fibonacci numbers F[k].) Use part

(b) to conclude that consecutive Fibonacci numbers are a worst-case input for Euclid's algorithm with respect to the number of recursive calls.