Finding GCD with Fibonacci: Base Case

[RoboNerd]

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

 

[tnich]

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

For a base case, chose the smallest (distinct) positive integers. How many divisions does it take to find their gcd? What are the corresponding fibonacci numbers?