Extending the Fibonacci sequence backwards, note that F0 = 0, F−1 = 1, and F−2 = −1.
Consider the terms of the sequence, modulo 109.
The number of distinct consecutive pairs of terms is 109 × 109 = 1018.
Hence, by the Pigeonhole Principle, there exists an identical pair of terms among the first 1018 + 1 pairs.
(The following is understood to be performed modulo 109.)
Suppose then that Fn Fn+k and Fn+1 Fn+k+1, where k 1018 + 1.
Working backwards, Fn−1 Fn+1 − Fn, and Fn+k−1 Fn+k+1 − Fn+k. Hence Fn−1 Fn+k−1.
Similarly, Fn−2 Fn+k−2, ... , F0 Fk, F−1 Fk−1, and F−2 Fk−2.
Hence Fk−2 −1.
Therefore Fk−2 will end in 999999999; that is, there does exist a Fibonacci number whose decimal representation ends in nine nines.
A very similar proof suffices to show that, for every positive integer m, there exists a positive integer k such that Fk is a multiple of m. Simply substitute m for 109, and m2 for 1018, in the above proof. We then conclude that F0 Fk (modulo m), for some k > 0.
Find the smallest n > 0 such that Fn ends in nine nines.
Does there exist a Fibonacci number whose decimal representation ends in 100?