0
$\begingroup$

QUESTION: Let $f:\mathbb{N}ā†’\mathbb{N}$ be the function defined by $f(0)=0$ ,$f(1)=1$ and $f(n)=f(n-1)+f(n-2)$ for all $nā‰„2$ , where $\mathbb{N}$ is the set of all non negative integers. Prove that $f(5n)$ is divisible by $5$ for all $n$.

MY ANSWER: It's clear that this is a Fibonacci sequence which goes like$ā†’$ $0,1,1,2,3,5,8,13,21,.......$

Now intuitively, we can see that $f(5n)$ is congruent to $0(mod 5)$. But how do I rigorously prove the same?

Any help is much appreciated. Thank you.

$\endgroup$
0
3
$\begingroup$

The Fibonacci recurrence relation holds modulo $5$ as well: You get one term by adding the two previous terms. Let's see what it looks like modulo $5$: $$ 1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, \ldots $$ We see that after each $0$, we get the same pattern: $0, a, a, 2a, 3a, 0$, for some $a$. This follows directly from the recurreence relation: After a $0$ there must be two identical terms, as the second $a$ is just $a+0$. After that must come $a+a = 2a$, then $a+2a = 3a$, and finally $2a+3a = 5a = 0$, bringing us back into another loop of the same pattern.

$\endgroup$
2
  • $\begingroup$ This was very well explained.. thank you so much.. just one query, may I consider it as a rigorous proof? $\endgroup$ – Stranger Forever May 11 '20 at 7:08
  • $\begingroup$ @StrangerForever I would think so, yes. But ultimately, it's up to whoever is doing the correcting. $\endgroup$ – Arthur May 11 '20 at 7:10
3
$\begingroup$

Use$$f_{5k+5}=f_{5k+4}+f_{5k+3}=2f_{5k+3}+f_{5k+2}=3f_{5k+2}+2f_{5k+1}=5f_{5k+1}+3f_{5k},$$so $5|f_{5k}\implies5|f_{5k+5}$.

$\endgroup$
1
$\begingroup$

Here's another way to look at the problem. The next number is in the Fibonacci sequence is determined by the previous two; you don't need to know its entire history. If you are working modulo $n$ then the number of possible states is $n^2$. You have a finite state machine. In your case, you are working modulo $5$ so $25$ states. You can map the transitions easily.

State $(0, 0)$ is dull it just stays where it is.

Starting at the usual state $(0, 1)$ gives this loop:

$$(0,1) \rightarrow (1,1) \rightarrow (1,2) \rightarrow (2,3) \rightarrow (3,0)$$ $$\rightarrow (0,3) \rightarrow (3,3) \rightarrow (3,1) \rightarrow (1,4) \rightarrow (4,0)$$ $$\rightarrow (0,4) \rightarrow (4,4) \rightarrow (4,3) \rightarrow (3,2) \rightarrow (2,0)$$ $$\rightarrow (0,2) \rightarrow (2,2) \rightarrow (2,4) \rightarrow (4,1) \rightarrow (1,0)$$

which then repeats. This is just Arthur's answer in a slightly different format.

That's $20$ states in a loop. Together with the trivial loop of $(0,0)$, that's $21$ states and there must be $4$ that did not occur. These form a loop.

$$(1,3) \rightarrow (3,4) \rightarrow (4,2) \rightarrow (2,1)$$

Similarly, you will find loops for any modulus but it is kind of a coincidence that every 5th Fibonacci number is a multiple of $5$. For example, work in modulus $2$ and you get a loop of $3$ not $2$. Every second number is not even. The pattern is odd, odd, even. In modulus $3$, you get a loop of $8$ states so not every 3rd is a multiple of $3$.

A little searching found this which looks interesting but I have not fully read it yet: The Period of the Fibonacci Sequence Modulo j.

$\endgroup$
3
  • $\begingroup$ Thank you so much.. your solution really helps too!.. I would like to ask you the same question as this method is quite similar to the previous one.. can this proof considered to be rigorous? Or does it solely depend on the teacher who corrects it? $\endgroup$ – Stranger Forever May 11 '20 at 19:32
  • $\begingroup$ @Stranger See here for more on this fundamental viewpoint, else you may end up painstakingly reinventing the $\rm\color{#c00}{wheel}\ (= \color{#c00}{\rm cycle}$ of a permutation)! $\endgroup$ – Bill Dubuque May 11 '20 at 22:23
  • $\begingroup$ @StrangerForever It is impossible for us to answer as we don't know enough about what you have covered so far and what your instructor expects. My answer and Arthur's rely on modulo arithmetic. If you have covered that previously and can use it then my answer should be good. Modulo arithmetic reduces the problem to a finite number of cases and it is reasonable to simply check all of those cases. If you have not covered modulo arithmetic then you would be better adapting Daniel's answer to avoid references to modulo arithmetic. $\endgroup$ – badjohn May 12 '20 at 8:41
0
$\begingroup$

Proof using induction. For the Base Case we have $$f_{5}=f_{5-1}+f_{5-2}=f_{4}+f_{3}=3+2=5\equiv0\pmod{5}$$ so the theorem holds for $n=1$.

Now you can use the recurrence directly on $f_{5n}$ to prove this holds in general for all $n\ge1$.

Now for the induction: Assume for some $k\in\mathbb{N}$ that $5$ divides $f_{5k}$. Hence \begin{align} f_{5k}&=f_{5k-1}+f_{5k-2}\\ &= f_{5(k-1)+4}+f_{5(k-1)+3} \equiv0\pmod{5} \end{align}

Now look at the $k+1$ case: \begin{align} f_{5(k+1)}&=f_{5(k+1)-1}+f_{5(k+1)-2}\\ &= f_{5k+4}+f_{5k+3}\\ &= (f_{5k+3}+f_{5k+2})+(f_{5k+2} +f_{5k+1})\\ &= f_{5k+3}+2f_{5k+2}+f_{5k+1}\\ &= 3f_{5k+2}+2f_{5k+1}\\ &= 3f_{5k+1}+3f_{5k}+2f_{5k+1}\\ &= 5f_{5k+1}+3f_{5k}\equiv0\pmod{5} \end{align} which holds true since by the inductive hypothesis we assumed $5\mid f_{5k}$.

$\endgroup$

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