5
$\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$
  • 7
    $\begingroup$ Yes............ $\endgroup$ – TheSimpliFire Jan 29 '18 at 9:39
  • 4
    $\begingroup$ crypto.ku.edu.tr/5th-Fibonacci and for another pattern, see: math.stackexchange.com/questions/2462222/… $\endgroup$ – Deepak Jan 29 '18 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$ – Mark Bennet Jan 29 '18 at 9:42
  • 4
    $\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$ – achille hui Jan 29 '18 at 9:46
  • 2
    $\begingroup$ Actually $$\nu_5(F_k) = \nu_5(k).$$ $\endgroup$ – Jack D'Aurizio Jan 29 '18 at 12:55
6
$\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$
  • $\begingroup$ This is useful. I'd only run the modulo up to F20 so I missed the emerging pattern. $\endgroup$ – Robbie Dee Jan 29 '18 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 '18 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 '18 at 22:53
12
$\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$
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$
2
$\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
$\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$

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.