13
$\begingroup$

How would you go about to prove that the final digits of the Fibonacci numbers recur after a cycle of 60?

References:

The sequence of final digits in Fibonacci numbers repeats in cycles of 60. The last two digits repeat in 300, the last three in 1500, the last four in , etc. The number of Fibonacci numbers between and is either 1 or 2 (Wells 1986, p. 65).

http://mathworld.wolfram.com/FibonacciNumber.html

  • 0
    Here is a link: http://oeis.org/A0963632018-12-14

5 Answers 5

1

I have found that there is an 11 number grouping. You must reduce numbers to a single digit (13=4 or 55=10=1). After 24 numbers into the sequence it repeats. To go a little deeper, a 9 is in the twelfth and twenty- fourth sequence and the real number is also divisible by 12 in these positions (which coincidentally is every twelfth number in the sequence).

Now if you do the multiplication table of numbers 1 through 8 and reduce all numbers to a single digit, you will find that 1 and 8 correspond in reverse with each other. The same for 2 and 7, also 4 and 5. 3 and 6 are different. You will notice that for every number sequence it will repeat after a 9 appears. So, Fibonacci sequence would be this:

1,1,2,3,5,8,4,3,7,1,8,9,8,8,7,6,4,1,5,6,2,8,1,9,1,1,2,3,5,8,4,3,7,1,8,9,8,8,7,6,4,1,5,6,2,8,1,9......

Remember how I said 1 and 8, 2 and 7, 4 and 5 correspond with each other by reducing the multiplication table to single digits and all numbers repeat a sequence after a 9?

If you move the eleven number sequence between the nines and set 1,1,2,3... above the sequence 8,8,7,6... You will find that they all correspond with the reducing method afore mentioned.

It's very interesting.

  • 0
    11 number grouping means the first$11$numbers in the sequence. The twelfth number is 144 and that reduces to$9$i.e.(1+4+4=9). Then a second set of eleven numbers followed by a reduced 9.2016-10-24
12

Since each term in the Fibonacci sequence is dependent on the previous two, each time a $0\pmod{m}$ appears in the sequence, what follows must be a multiple of the sequence starting at $F_0,F_1,\dots=0,1,\dots$ That is, a subsequence starting with $0,a,\dots$ is $a$ times the sequence starting with $0,1,\dots$

Consider the Fibonacci sequence $\text{mod }2$: $ \color{red}{0,1,1,}\color{green}{0,1,1,\dots} $ Thus, the Fibonacci sequence repeats $\text{mod }2$ with a period of $3$.

Consider the Fibonacci sequence $\text{mod }5$: $ \color{red}{0,1,1,2,3,}\color{green}{0,3,3,\dots} $ Thus, the Fibonacci sequence is multiplied by $3\pmod{5}$ each "period" of $5$. Since $3^4=1\pmod{5}$, the Fibonacci sequence repeats $\text{mod }5$ with a period of $20=4\cdot5$.

Thus, the Fibonacci sequence repeats $\text{mod }10$ with a period of $60=\operatorname{LCM}(3,20)$.

9

Notice that:

$F_{n+15} \equiv 7F_n \pmod{10}$ for $n\geq 1$.

Also the order of $7$ mod $10$ is $4$ so the repetition in the digits of the Fibonacci numbers begins after place $15\times 4 = 60$.

  • 0
    In [my answer](http://math.stackexchange.com/a/113602/), it is shown that $F_{n+5}\equiv3F_n\pmod{5}$ and $F_{n+3}\equiv F_n\pmod{2}$. Thus, we get that $F_{n+15}\equiv2F_n\pmod{5}$ and $F_{n+15}\equiv F_n\pmod{2}$. The [Chinese Remainder Theorem](http://en.wikipedia.org/wiki/Chinese_remainder_theorem) then says that $F_{n+15}\equiv7F_n\pmod{10}$. That's$a$different way than computing $16$ terms.2012-02-26
9

Note that

$ \begin{pmatrix} F_{n+1}\\ F_{n+2} \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} F_n \\ F_{n+1} \end{pmatrix} $

and

$ \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^{60} \equiv \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \mod 10. $

One can verify that $60$ is the smallest power for which this holds, so it is the order of the matrix mod 10. In particular

$ \begin{pmatrix} F_{n+60}\\ F_{n+61} \end{pmatrix} \equiv \begin{pmatrix} F_n \\ F_{n+1} \end{pmatrix} \mod 10 $

so the final digits repeat from that point onwards.

  • 3
    The same matrix applies to the [Lucas Numbers](http://en.wikipedia.org/wiki/Lucas_number), however, $\text{ mod }10$, they have a period of $12$. The fact that \begin{pmatrix} 0&1\\1&1\end{pmatrix}^{60}=\begin{pmatrix}1&0\\0&1\end{pmatrix}\text{ mod }10, says that the period of a sequence satisfying $a_n=a_{n-1}+a_{n-2}$ divides $60$.2012-02-26
5

$F_{0}=F_1=F_{60}=F_{61}= 1 \mod10$

By inspection, these are the first two pairs of consecutive Fibonaccis for which this is true. Since the recurrence relation only takes into account the previous two terms and last digits only depend on previous last digits, this suffices to prove the claim.