Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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}$.
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$.
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$.)
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}$$
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$.
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.
