# Solution to puzzle 85: Fibonacci nines

Does there exist a Fibonacci number whose decimal representation ends in nine nines?

(The Fibonacci numbers are defined by the recurrence equation F_{1} = 1, F_{2} = 1, with F_{n} = F_{n−1} + F_{n−2}, for n > 2.)

Extending the Fibonacci sequence backwards, note that F_{0} = 0, F_{−1} = 1, and F_{−2} = −1.

Consider the terms of the sequence, modulo 10^{9}.

The number of distinct consecutive pairs of terms is 10^{9} × 10^{9} = 10^{18}.

Hence, by the Pigeonhole Principle, there exists an identical pair of terms among the first 10^{18} + 1 pairs.

(The following is understood to be performed modulo 10^{9}.)

Suppose then that F_{n} F_{n+k} and F_{n+1} F_{n+k+1}, where k 10^{18} + 1.

Working backwards, F_{n−1} F_{n+1} − F_{n}, and F_{n+k−1} F_{n+k+1} − F_{n+k}. Hence F_{n−1} F_{n+k−1}.

Similarly, F_{n−2} F_{n+k−2}, ... , F_{0} F_{k}, F_{−1} F_{k−1}, and F_{−2} F_{k−2}.

Hence F_{k−2} −1.

Therefore F_{k−2} will end in 999999999; that is, there *does* exist a Fibonacci number whose decimal representation ends in nine nines.

## Remarks

A very similar proof suffices to show that, for every positive integer m, there exists a positive integer k such that F_{k} is a multiple of m. Simply substitute *m* for 10^{9}, and *m*^{2} for 10^{18}, in the above proof. We then conclude that F_{0} F_{k} (modulo m), for some k > 0.

## Follow-up questions

Find the *smallest* n > 0 such that F_{n} ends in nine nines.

Does there exist a Fibonacci number whose decimal representation ends in 100?

## Further reading

- Fibonacci Numbers and the Golden Section
- Phi: That Golden Number
- Fibonacci Number
- Golden Ratio

Source: Fibonaccian nines, on flooble :: perplexus

Back to top