>>559
a = r[0] = q* b + r[2] ≧ b + r[2]
b = r[1] = q'*r[2] + r[3] ≧ r[2] + r[3]
...
r[R-3] ≧ r[R-2] + r[R-1]
r[R-2] ≧ r[R-1] + r[R]
r[R-1] ≧ r[R] + 0
逆に辿って、
r[R-1] ≧ 1 + 0 = Fib[1]
r[R-2] ≧ Fib[1] + 1 = Fib[2]
r[R-3] ≧ Fib[2] + Fib[1] = Fib[3]
.... r[0] ≧ Fib[R]
Fib[n] ≧ a ≧ Fib[R]
よって n ≧ R