10
$\begingroup$

It's well known that the Fibonacci sequence $\pmod m$ (where $m \in \mathbb N$) is periodic. I have figured out a proof for this, but upon googling, I found proofs online that were far more complicated. This leads me to suspect that my proof may be fallacious - that's why I am posting here.

Proof:

Let us list out the Fibonacci sequence modulo m, where m is some integer. It will look something like this at first (for $10$ at least):

$$ 1,2, 3,5,8, 3,1, 4, 5, 9, 4, 3, 7 {\dots}$$

Obviously, any number in the sequence is the sum of the last two numbers modulo $m$. Therefore, if at any point in the series modulo m a pair of numbers repeat, the numbers following that pair must repeat as well. eg. if at some point later we see the pair $1, 1$, then $2, 3, 5, \dots$ must follow that pair.

Now there are $m^2$ possible pairs in the series $\text{mod} m$. By the pigeonhole principle, after $m^2 + 1$ terms, a pair must repeat. If a pair repeats once, it must repeat again the same number of terms later. Therefore, the Fibonacci sequence $\pmod m$ is periodic $\forall m$ .

Is my proof correct?

$\endgroup$

marked as duplicate by Jyrki Lahtonen Jul 30 '15 at 9:05

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 3
    $\begingroup$ Your proof is correct. It happens to be the first proof I ever saw for this fact. IMHO it is the simplest, too! $\endgroup$ – Jyrki Lahtonen Jan 8 '14 at 9:11
  • $\begingroup$ See here $\endgroup$ – rah4927 Jan 9 '14 at 12:20
  • $\begingroup$ I have this same question now and since there's already a question mine woukd get closed as a duplicate. So, I'll ask my clarification here. $\endgroup$ – user230452 Feb 28 '16 at 2:31
  • $\begingroup$ If any one pair repeats, the enitre sequence after that repeats and the Pigeonhole Principle says that at least one pair must repeat. But, what we have to prove os that the FIRST pair repeats specifically. How do we do that? $\endgroup$ – user230452 Feb 28 '16 at 2:32
9
$\begingroup$

No, you haven't proven yet that the Fibonacci sequence is periodic ($\exists t, \forall n, F(n+t) = F(n)$), you have proven that it is eventually periodic ($\exists t, \exists n, \forall m, m \ge n \implies F(m+t) = F(m)$)

If you have a finite set $S$ (here, the set of pairs modulo $m$) and a function $f :S \to S$, any sequence obtained by iterating $f$ on some element of $S$ is eventually periodic, by the pigeonhole principle. If you want every such sequence to be periodic, you need $f$ to be a bijection :

If $f$ is a bijection and $F(n+1+t) = F(n+1)$ for some $n$, then by applying $f^{-1}$ we get $F(n+t) = F(n)$, and we repeat until we obtain $F(t) = F(0)$.

If $f$ is not bijective, it is not surjective, so if you start your sequence on some element not in the image of $f$, it will never be periodic because that element can't appear again in the sequence.

Here, $f(a,b) = (b,a+b)$, which is a bijection because its inverse is given by $f^{-1}(a,b) = (b-a,a)$

$\endgroup$
  • 3
    $\begingroup$ Just to clarify, if it is eventually periodic it will get into a repeating pattern eventually. If it is (strictly) periodic, it starts in the repeating pattern. $\endgroup$ – Arthur Jan 8 '14 at 9:50
  • $\begingroup$ eventually periodic is also known as preperiodic. See en.wikipedia.org/wiki/Periodic_point. $\endgroup$ – lhf Jan 8 '14 at 9:51
  • $\begingroup$ Can you explain what the function $f$ does please? What does it mean to iterate $f$? $\endgroup$ – user230452 Feb 28 '16 at 2:43
  • $\begingroup$ @user230452 iterating $f$ on an element $x$ means computing the sequence $x,f(x),f(f(x)),f(f(f(x)))$ etc $\endgroup$ – mercio Feb 28 '16 at 11:03
  • $\begingroup$ Your proof is beautiful. It took me two days to understand it :) $\endgroup$ – user230452 Feb 28 '16 at 13:08

Not the answer you're looking for? Browse other questions tagged or ask your own question.