Introduction
In this article we are going to talk about an interesting cyclic phenomena of the Fibonacci Numbers.
First of all for dummies let us recall Fibonacci Numbers :
The Fibonacci numbers are the numbers in the integer sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, … defined by the recurrence relation
F2 = 1
Fi = Fi-1 + Fi-2
Motivation
Now if we try to observe the parity of the numbers in the Fibonacci sequence
we get odd(1), odd(1), even(2), odd(3), odd(5), even(8), · · ·
We observe that the cyclic pattern of odd-odd-even is popping up in the sequence and with simple reasoning it can be shown that this cyclic pattern will always continue.
Now let us try to change the perspective and denote the terms having odd parity by 1 and even parity by 0. So our modified sequences becomes 1, 1, 0, 1, 1, 0, 1, 1, 0, · · ·
And we try to ask ourselves a question ”Can we apply some operation on the Fibonacci Sequence and get this modified version?”. After a bit of thought we realize that we can get it by noting down the remainder we get by dividing the original terms by 2. More technically we call it modulo 2 of the number.
Now we have seen we get this periodic sequence out of Fibonacci Sequence by dividing by 2 and noting the remainders. We now can be a bit curious and try to divide by 3 and note the remainders. So after doing that we will again 1 get the cyclic pattern and it is 1−1−2−0−2−2−1−0 (check it by yourself!).
But we can divide by any natural number ’n’ and note down the remainders. So finally we can ask ourselves ”Does this happen in general with any such ’n’? It turns out we always get a repeating sequence and ”PIGEONHOLE PRINCIPLE” can actually help us to figure out why.
How? Here’s the proof:
So what we are going to do is to look at the consecutive pair of numbers and
record their remainders like for instance consider the case of n = 2
(1, 1),(1, 2),(2, 3),(3, 5), · · · ⇒ (1, 1),(1, 0),(0, 1),(1, 1), · · · So our pigeons
are going to be the pairs of consecutive Fibonacci Numbers, i.e., (Fn, Fn+1).
Note that we have infinite pigeons!
Our holes are going to be all possible pairs of remainders we can get after dividing by ‘n’
. We denote the pairs of remainders corresponding to (Fn , Fn+1 )
by (Rn , Rn+1 ).
Holes −> {(h, k) | 0 ≤ h ≤ n − 1, 0 ≤ k ≤ n − 1}.
As there are n possibilities for each of the coordinates, we have total of n2 possibilities. So we have n2 holes.
As there are more pigeons than the holes present by Pigeonhole Principle
we must have 2 different pairs having the same set of remainders.
So ∃m, n ∈ N such that (Fn, Fn+1) = (Fm, Fm+1) and m < n ⇒ Rm = Rn
and Rm+1 = Rn+1
Because any number is the sum of the previous 2 numbers in the sequence. Once
we know what remainders are for a pair we can actually find the remainder for
the subsequent number. But as first 2 remainders are same the next one also
be same.
But then this implies the very next pairs also repeat, i.e.,
(Fn+1, Fn+2) = (Fm+1, Fm+2). Recursively applying this argument our sequence of remainder will become eventually periodic. But note that given Fn
and Fn+1 we can also get Fn-1. So by knowing the remainders for a pair we
can also find the remainder for the previous number.
Hence sequences of remainders become periodic.
Remarks:
- n − m actually is how far we need to go for repetition. We might go even shorter to get repetition.
- The period with which the sequence of Fibonacci numbers taken modulo n repeats is known as the nth Pisano Period. Pisano periods are named after Leonardo Pisano, better known as Fibonacci.