Prove that for all $n \in Z^+$, Euclid’s algorithm applied to the pair $(f_{n+1}, f_{n+2})$, takes $n$ steps.

Question

Prove that for all $n \in Z^+$, Euclid’s algorithm applied to the pair $(f_{n+1}, f_{n+2})$, takes $n$ steps. (Here, as previously, $f_n$ denotes the nth Fibonacci number.)

I don't understand how to apply this algorithm with the use of actually numbers, and I tried to prove by induction, but was unsure as to how to do the inductive step.

Answer 1

The expression $f_{n+2} = f_{n+1} + f_n$ that defines Fibonacci numbers is the Euclidean division of $f_{n+2}$ by $f_{n+1}$ with remainder $f_n$.

The last step in Euclid’s algorithm is $f_3 = 2 f_2 + 0$, and so $n$ steps are taken.