- #1
RoboNerd
- 410
- 11
Homework Statement
Suppose that m divisions are required to find gcd(a,b). Prove by induction that for m >= 1, a >= F(m+2) and b>= F(m+1) where F(n) is the Fibonacci sequence.
Hint: to find gcd(a,b), after the first division the algorithm computes gcd(b,r).
Homework Equations
Fibonacci Sequence: [/B]F(n) = F(n-1) + F(n-2)
Euclidean algorithm for finding the GCD of two numbers.
The Attempt at a Solution
[/B]
Hi everyone,
I know that the fibonacci sequence [F(n) = F(n-1) + F(n-2)] looks a lot like the expression
num = q*x + r, which is the expression for a number being divided by x with a quotient q and remainder r.
I know that I am supposed to prove by induction that for m >= 1, a >= F(m+2) and b>= F(m+1) where F(n) is the Fibonacci sequence, but I have no idea how to get started even with the base case or how to prove it.
Any guidance would be greatly appreciated. Thanks