Before revision: The Fibonacci numbers are defined by and for The above relations show that and , by induction, So, if the Euclidean algorithm requires steps, one has One has for every integer , where is the Golden ratio.
After revision: The Fibonacci numbers are defined by and for The above relations show that and By induction, So, if the Euclidean algorithm requires steps, one has One has for every integer , where is the Golden ratio.