with
equality exactly at n = 0 = F
2
2 − 1. Thus the theorem is true for integers of this form.
For other values of n we proceed by induction. Suppose n satisfies Fm ≤ n < Fm+1 − 1
for some m ≥ 4, and that the theorem is true for all integers less than n. Then