Why are Fibonacci numbers bad for Euclid's Algorithm and how to derive this upper bound on number of steps needed in general? I want to ask two things.
The first is why are consecutive Fibonacci numbers the worst case for Euclid's algorithm? I keep seeing people say it in passing and I understand that it's really bad, but how do we know it's the worst?
The second question is about an upper bound on the number of applications of the division algorithm needed to compute the GCD of two distinct positive integers. I am given a hint that it will be of the form $c \log b + d$ when $c, d$ are constants and $b$ is the smaller of the two numbers you start with. 
I have seen someone mention that it is $\frac{1}{2} \log b + 1$ but again, I don't know how to derive this and would very much appreciate a hint or push in the right direction. 
Thank you in advance!

You can prove this using induction on the number of gcd() calls.
To prove: If a pair (a,b) takes n steps to compute the gcd, then

*

*a >= F_(k+2)

*b >= F_(k+1)
With one assumption a >= b

Base case n = 1, the lemma is true.
Consider the lemma to be true for n = k - 1, k > 1
Let a pair (a,b) be such that it takes k steps to compute the gcd.
Hence (b, a mod b) will take k - 1 steps.
Thus b >= F_(k+1) ... by hypothesis
And a mod b >= F_(k)
Now, a = b×q + a mod b >= b + a mod b >= F_(k+1) + F_(k) >= F(k+2)
Hence we have proven that consequentive fibonacci numbers are the worst case. More specifically, they are the least of the numbers to take a certain arbitrary number of steps.
