Question

Determine the number of divisions used by the Euclidean algorithm to find the greatest common divisor of the Fibonacci numbers ${\mathbf{f}}_{\mathbf{n}}$and ${\mathbf{f}}_{\mathbf{n}\mathbf{+}\mathbf{1}}$, where n is a nonnegative integer. Verify your answer using mathematical induction.

Short answer

$\mathrm{n}\ge 2:\mathrm{n}-1\mathrm{divisions}$

Step-by-step solution

The Euclidean Algorithm

The Euclidean Algorithm determines the greatest common divisor by dividing one integer by the other.

$\begin{array}{r}\mathrm{f}\left(0\right)=0\\ \mathrm{f}\left(1\right)=1\\ {\mathrm{f}}_{\mathrm{n}}={\mathrm{f}}_{\mathrm{n}-1}+{\mathrm{f}}_{\mathrm{n}-2}\text{when}\mathrm{n}\ge 2\end{array}$

To prove that number of divisions by Euclidean Algorithm for fn and fn+1 is n-1 when n > 2  

The proof is given by INDUCTION:

The number of divisions is n - 1 when n > 2

Let P(n) be the number of divisions by the Euclidean Algorithm for $f_n$and $f_{n+1}$

Is n - 1 when n > 2 .

Inductive step: Assume that P(k) is true.

To prove that P(K+1) is also true.

Therefore, it can be written as by executing the Euclidean Algorithm:

$f_{k+1}=1\cdot f_k+f_{k-1}\text{[use the definition:}{f}_n=f_{n-1}-f_{n-2}\text{]}$

Then, divide $f_k$by $f_{k-1}$which is the same as the initial step of the Euclidean Algorithm of $f_k$and $f_{k-1}$.

Also, (k - 1) + k = k

Hence, k divisions are required while n - 1 = (k + 1) - 1 = k

Thus, it is proved that P (k + 1) is true.