Skip to main content.

Solution to puzzle 85: Fibonacci nines

Skip restatement of puzzle.Does there exist a Fibonacci number whose decimal representation ends in nine nines?
(The Fibonacci numbers are defined by the recurrence equation F1 = 1, F2 = 1, with Fn = Fn−1 + Fn−2, for n > 2.)

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 congruent to Fn+k and Fn+1 congruent to Fn+k+1, where k less than or equal to 1018 + 1.
Working backwards, Fn−1 congruent to Fn+1 − Fn, and Fn+k−1 congruent to Fn+k+1 − Fn+k.  Hence Fn−1 congruent to Fn+k−1.
Similarly, Fn−2 congruent to Fn+k−2, ... ,  F0 congruent to Fk,  F−1 congruent to Fk−1,  and F−2 congruent to Fk−2.
Hence Fk−2 congruent to −1.

Therefore Fk−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 Fk is a multiple of m.  Simply substitute m for 109, and m2 for 1018, in the above proof.  We then conclude that F0 congruent to Fk (modulo m), for some k > 0.

Follow-up questions

Find the smallest n > 0 such that Fn ends in nine nines.

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

Further reading

  1. Fibonacci Numbers and the Golden Section
  2. Phi: That Golden Number
  3. Fibonacci Number
  4. Golden Ratio

Source: Fibonaccian nines, on flooble :: perplexus

Back to top