6
$\begingroup$

There seems to be a pattern of sorts in the Fibonacci sequence:

The $5$th, $10$th, $15$th & $20$th values are:

$$5, 55, 610, 6765$$

Does this pattern continue ad infinitum? I've tried a few more using Binet's Formula and it seems to hold. So:

Is every $N$th Fibonacci number where $N$ is divisible by $5$ itself divisible by $5$?

Bonus Q: Are there any other patterns?

$\endgroup$
5
  • 4
    $\begingroup$ crypto.ku.edu.tr/5th-Fibonacci and for another pattern, see: math.stackexchange.com/questions/2462222/… $\endgroup$
    – Deepak
    Jan 29, 2018 at 9:41
  • 2
    $\begingroup$ If you want to investigate yourself, there is a relationship between Fibonacci and Lucan numbers which would enable you to prove that $F_n|F_{kn}$ for all positive integers $n$ and $k$. Always more satisfying to do yourself and you have Binet and the equivalent expression for Lucas nos not too difficult to find a useful expression for $F_{n+m}$ (induction is also a route) $\endgroup$ Jan 29, 2018 at 9:42
  • 5
    $\begingroup$ Fibonacci numbers is an example of a strong divisibility sequence. It satisfies for all positive integers $m, n$. $\gcd(a_m,a_n) = a_{\gcd(m,n)}$. As a corollary, $a_m | a_{km}$ for any positive integers $k,m$ . Since $F_5 = 5$, you have $ 5 = F_5 | F_{5k}$ for every $k$. $\endgroup$ Jan 29, 2018 at 9:46
  • 3
    $\begingroup$ Actually $$\nu_5(F_k) = \nu_5(k).$$ $\endgroup$ Jan 29, 2018 at 12:55
  • 1
    $\begingroup$ I discussed some relationships between Fibonacci numbers and primes here $\endgroup$
    – Joffan
    Jan 29, 2018 at 15:28

6 Answers 6

15
$\begingroup$

The answer is YES.

Use induction for $n=1, 2, ...$

$F_{5\cdot1}=5$ holds so we have a basis for induction.

Suppose $F_{5k}=5t$ for some $t\in\mathbb{N}$. Then consider $n=k+1$:

$$\begin{align}F_{5k+5}&=F_{5k+3}+F_{5k+4}\\&=2F_{5k+3}+F_{5k+2}\\&=2(F_{5k+2}+F_{5k+1})+F_{5k+1}+F_{5k}\\&=3F_{5k+1}+2F_{5k+1}+F_{5k}+2F_{5k}\\&=5F_{5k+1}+3(5t)\\&=5(F_{5k+1}+3t)\end{align}$$ This is clearly divisible by $5$ so $5\mid F_{5n}$ for $n\in\mathbb{N}$.

$\endgroup$
8
$\begingroup$

Let us make a table of the Fibonacci sequence modulo $5$. If we can find two occurrences of the same two terms modulo $5$ with all the $F_{5k}$ (between those two occurence) being $0$ modulo $5$, we can prove this statement.

$$\begin{array}{c|c|c|} \text{$F_1$ to $F_5$} & \text{1} & \text{1} & \text{2} & \text{3} & \text{0} \\ \text{$F_6$ to $F_{10}$} & \text{3} & \text{3} & \text{1} & \text{4} & \text{0} \\ \text{$F_{11}$ to $F_{15}$} & \text{4} & \text{4} & \text{3} & \text{2} & \text{0} \\ \text{$F_{16}$ to $F_{20}$} & \text{2} & \text{2} & \text{4} & \text{1} & \text{0} \\ \text{$F_{21}$ to $F_{25}$} & \text{1} & \text{1} & \text{2} & \text{3} & \text{0} \\ \end{array}$$

Since $F_1$ and $F_2$ are the same as $F_{21}$ and $F_{22}$, and $F_5$, $F_{10}$, $F_{15}$ and $F_{20}$ are all $0$, then this cycle repeats indefinitely, and hence $F_{5k} \equiv 0 \pmod 5$.

$\endgroup$
3
  • $\begingroup$ This is useful. I'd only run the modulo up to F20 so I missed the emerging pattern. $\endgroup$
    – Robbie Dee
    Jan 29, 2018 at 13:16
  • $\begingroup$ @RobbieDee Yeah, the problem is that 20 is the period, so you need 25 to verify it ;-) $\endgroup$
    – yo'
    Jan 29, 2018 at 16:35
  • $\begingroup$ @RobbieDee Thanks for the upvotes! I'm surprised no one used this method, but it doesn't take too long until you see a pattern (because $5$ is a small number). $\endgroup$
    – Toby Mak
    Jan 29, 2018 at 22:53
5
$\begingroup$

If $F_n$ is divisible by $5$, then so is $F_{n+5}$ because $$ F_{n+5} = 8 F_n + 5 F_{n-1} $$ The result follows by induction. The base of the induction is $F_5=5$, which is divisible by $5$. (You can also use $F_0=0$.)

$\endgroup$
1
3
$\begingroup$

Yes, if $5$ divides $n$ then $5$ divides $F_n$. Actually also the other way round is true, so $5$ divides $n$ if and only if $5$ divides $F_n$.

More generally, the following congruence holds $$F_n\equiv n3^{n-1}\pmod{5}.$$ This congruence implies our claim and more than that. For example, it follows that the Fibonacci sequence modulo $5$ is periodic with period length $5\cdot 4=20$ where $5$ is the period of $n$ and $4$ the period of $3^{n-1}$ (recall that by Fermat's little theorem $3^{k(5-1)}\equiv 1 \pmod{5}$). The list of values $F_n\pmod{5}$ is $$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline n \pmod{20}& 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 &9\\ F_n\pmod{5} &\mathbf{0}& 1& 1& 2& 3& \mathbf{0}& 3& 3& 1& 4\\ \hline n \pmod{20}&10& 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18&19\\ F_n\pmod{5} &\mathbf{0}& 4& 4& 3& 2& \mathbf{0}& 2& 2& 4& 1 \\\hline \end{array}$$

Proof of the above congruence $F_n\equiv n3^{n-1}\pmod{5}$. By the Binet's formula and the binomial theorem we have that $$\begin{align}F_n&=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)\\ &=\frac{1}{2^{n}\sqrt{5}}\sum_{k=0}^{n}\binom{n}{k}\left((\sqrt{5})^k-(-\sqrt{5})^k\right)\\ &=\frac{1}{2^{n}\sqrt{5}}\sum_{j=0}^{\lfloor (n-1)/2\rfloor}\binom{n}{2j+1}\left((\sqrt{5})^{2j+1}-(-\sqrt{5})^{2j+1}\right)\\ &=\frac{1}{2^{n}\sqrt{5}}\sum_{j=0}^{\lfloor (n-1)/2\rfloor}\binom{n}{2j+1}(2\sqrt{5}\cdot 5^j)\\ &=\frac{1}{2^{n-1}}\sum_{j=0}^{\lfloor (n-1)/2\rfloor}\binom{n}{2j+1}5^j \equiv 3^{n-1}\sum_{j=0}^{0}\binom{n}{2j+1}5^j\equiv n3^{n-1}\pmod{5}. \end{align}$$

$\endgroup$
0
0
$\begingroup$

We know that the fifth Fibonacci number is $5$. Then, we let this be $x$th number. The next number is defined by the $(x+x-1)$th number. The next will be $(2x-1+x)$th. Then the next is $(3x-1+2x-1)$th. The next is $(8x-3)$. The next is $(13x-5)$. This means that the $(5k+5)$th term can be expressed as $13\times 5k$th term $-5$. This is evidently a multiple of 5, since the first term with $5k=5$, $5$, is a multiple of $5$.

$\endgroup$
0
$\begingroup$

The fibonacci series follows the same rule as $\frac{a^n-b^n}{a-b}$ as applied to integers. Here, $a=\frac 12\sqrt{-1}; \ b=\frac 12\sqrt{-5}$. They are in essence, repunits, or numbers written entirely in '1's. So 111 will divide 6 and 9 1's but not 7 or 10.

If some number $x$ divides some $F_y$, then it divides every $F_{yz}$. As with ordinary numbers, it suffices to deal with prime and prime powers, the composite numbers being a weak multiplication (eg LCM for product), so 10 divides $F_{15n}$ for all n, and no other.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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