a, b を

a ≧ b ≧ 0

を満たす整数とする。


a, b の最大公約数をユークリッドの互除法で求める際、
余りを計算する回数を R(a, b) と書くことにする。

(F_n) は フィボナッチ数列 0, 1, 1, 2, 3, …, とする。

n を F_n ≧ a ≧ b ≧ 0 を満たす整数とするとき、

R(a, b) ≦ n

が成り立つことを示せ。