Homework answers / question archive /  Consider Euclid GCD for consecutive Fibonacci numbers (Fib(m),Fib(m - 1))

 Consider Euclid GCD for consecutive Fibonacci numbers (Fib(m),Fib(m - 1))

Computer Science

Share With

 Consider Euclid GCD for consecutive Fibonacci numbers (Fib(m),Fib(m - 1)). a) [6pts] Compute the number of iterations T performed in terms of m.

b) [12pts] Using Mathematical Induction (strong form) prove that 1.5m < Fib(m) < 2m for all m ≥ 11.

c) [7pts] Now let n be the input size, i.e., the number of binary digits of Fib(m). From PSN exercise we know that n ≈ log2Fib(m). For convenience, you may take n = log2Fib(m). Obtain bounds for the number of iterations T performed in terms of the input size n.