Fibonacci sequence divisible by 7?

Question

Make and prove a conjecture about when the Fibonacci sequence, $F_n$, is divisible by $7$.

I've realized it's when $n$ is a multiple of $8$. I just don't know how to go about proving it.

Answer 1

Look at the sequence $F_n$ reduced mod $7$:

1,1,2,3,5,1,6,0,6,6,5,4,2,6,1,0, 1,1,2.. and it repeats forever

Since the only places where it is 0 are $n=8,16$ this proves that $7|F_n \iff 8|n$.

---

General theory of recurrence relations.

Definition A $k$th order recurrence relation on some set $X$ is a function $a : \mathbb N \rightarrow X$ with $k$ initial values i.e. $a(1),\cdots,a(k)$ defined and for all $i > k$, $a(i+k+1) = f(a(i),a(i+1),\cdots,a(i+k))$. Note that a $k$th order recurrence is also a $k+1$th order recurrence.

Notation We generally write the elements of a $k$th order recurrence relation as $(a_n)$.

Definition Recurrence relation homomorphisms, let $(a_n)$ be a $k$th order recurrence relation on the set $X$ defined by the map $f : X^k \rightarrow X$ (as well as some initial values). A map $\varphi : X -> Y$ is called a recurrence relation homomorphism on $a$ when there exists $f' : Y^k \rightarrow Y$ satisfying the commutative diagram $\varphi \circ f = f' \circ \varphi$.

Theorem Recurrence relation homomorphisms produce recurrence relations. Suppose we are given a recurrence relation homomorphism in the notation above. The claim is that $b_n = \varphi(a_n)$ is also a $k$th order recurrence relation.

Proof Clearly $k$ initial values are given, further for $i > k$ we have $b_{i+k+1} = \varphi(f(a_{i},a_{i+1},\cdots,a_{i+k})) = f'(\varphi(a_{i}),\varphi(a_{i+1}),\cdots,\varphi(a_{i+k}))) = f'(b_{i},b_{i+1},\cdots,b_{i+k}).$

Example The "reduction mod m" map $\varphi : \mathbb Z \rightarrow \mathbb Z/m\mathbb Z$ as described here is a recurrence homomorphism on any recurrence defined by a polynomial. To see this note that homomorphisms on rings (such as $\varphi$) can be lifted to homomorphisms on polynomial rings over the respective rings. That induces the map from $f$ to $f'$.

Example Call the Fibonacci sequence $(F_n)$ reduced mod 7: $(S_n)$, this is a recurrence by the general example above. Note that $F_n \equiv S_n \pmod 7$.

Theorem Initial segments may be discarded. Suppose $a_n$ is a recurrence relation of order $k$, then $b_n = a_{n+h}$ for any constant $h$ is also a recurrence relation of order $k$.

Proof Initial values are computed easily, if $f$ is the function defining elements of $a$ then $f$ also defines elements of $b$, to see this note that for $i > k$ we have $b_i = a_{i+h} = f(a_{i+h},a_{i+1+h},\cdots,a_{i+k+h}) = f(b_{i},b_{i+1},\cdots,b_{i+k})$.

Theorem Periodicity. Suppose the recurrence relation $b_n$ is defined as $a_{n+h}$ (both being $k$th order), if they share the first $k$ initial values then they are equal everywhere.

Proof Induction on $n$ in the stronger proposition that for all $i \le n$, $a_i = b_i$.

• base case (n = k): This is the hypothesis of the theorem.

• recursive step ($n \implies n+1$): Since for every $i \le n$, $a_i = b_i$ we have $a_{n+1} = f(a_{n-k},a_{n-k+1},\cdots,a_{n}) = f(b_{n-k},b_{n-k+1},\cdots,b_{n}) = b_{n+1}$ (since they are both defined by $f$).

Example Define $S'_n = S_{n+16}$ they share the first two initial values therefore they are equal everywhere.

Example Define $S_n^r = S_{n+16\cdot r}$ by induction these are all equal: The base case $r=0$ is trivial and the recursive step $r \implies r+1$ comes form an adaptation of the previous example and transitivity.

Theorem $7|F_n \iff 8|n$.

Proof By the previous examples we have seen that $F_n \equiv F_{n+16\cdot r} \pmod 7$, furthermore a direct computation of the first 16 values of $S_n$ (at the top) shows that $F_n \equiv 0 \pmod 7 \iff n = 0+16 \cdot r,8+16\cdot r$ this is equivalent to $8|n$ and $x = 0 \pmod m$ is equivalent to $m|x$.

Answer 2

A more pedestrian approach of induction, looking at the first 16 fibonacci numbers, the only 2 which are divisible by 7 are $f_8=21$ and $f_{16}=987$. Conjecture that $f_n$ is divisible by 7 if and only if $n$ is divisible by 8, as you mention in the comments. Using these observations as the base case, assume the result holds for all $f_j$ for $j\leq n$. Notice

$$ f_{n+1}=21f_{n-6}+13f_{n-7} $$

which can be worked out by continually applying the recursive definition of the fibonacci sequence. This equation makes the induction follow pretty easily.

Answer 3

Hint $\ $ Consider the shift map $\rm\:n\to n+1\:$ on the pairs $\rm\:(f_{n-1},\:f_n)\,\ \ (mod\ 7)\:.$ Below is a further hint from one of my old sci.math posts. See this answer for much more.

---

> A sequence f(n) satisfies the relation f(n+2) = [f(n+1)]^2 - f(n), 
> with f(1) = 39 and f(2) = 45.  Prove that 1986 divides infinitely 
> many terms of the sequence. 

Since the recursion determines unique values $\rm\:f_{n+2},\:f_n\:$ when run fore/backward, the shift map on the sequence induces a permutation $\rm\:F\:$ on integer pairs $$\rm mod\ 1986\!:\ \ F(f_n,f_{n+1})\ =\ (f_{n+1},f_{n+2})\ \quad i.e.\quad F(a,b)\: =\ (b,\,b^2-a)\ \ $$ But $\:0\:$ occurs in the cycle containing $(39,45)$ since $\rm\:F(39,45)\: =\: (45,0),\:$ so $\:0\:$ occurs infinitely often in this finite cycle when $\rm\:F\:$ is iterated.

This replaces less formal arguments elsewhere on "repeated blocks" by rigorous arguments on standard structures (permutations and their cycle decomposition), thus clarifying the essence of the matter. One should strive to learn to recognize these abstractions in the wild, else one will be doomed to continually reinvent the wheel (here cycle).

Answer 4

There is a cool thing with the Fibonacci and number 7, it transforms to a sequence of 16 number that repeat infinitely.

0 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

0,1,1,2,3,5,1,6,0,6,6,5,4,2,6,1,0

If you keep with the sequence you can see there is a 0 every 8th position so this let us with two slices of sequence.

s1 : 1,1,2,3,5,1,6 s2 : 6,6,5,4,2,6,1

So finobacci in module 7 will be like: 0s10s20s10s2........

If you take a consecutive s1 , s2 and add them number by number:

s1 : 1,1,2,3,5,1,6

s2 : 6,6,5,4,2,6,1 +

     7,7,7,7,7,7,7

Which in module 7 is 0 so Fibonacci is transformed into a sequence of infinite 0.

So the process will be the following: 1. Module 7 to Fibonacci sequence.

0,1,1,2,3,5,1,6,0,6,6,5,4,2,6,1,0,1,1,2,3,5,1,6,0,6,6,5,4,2,6,1,0,1,1,2,3,5,1,6,0,6,6,5,4,2,6,1,0....

2. Group them by groups of 8 numbers.

3. If you take all groups of s1 and add them with their respective s2, consecutive. The result should be an infinite sequence of 0.

Answer 5

The Fibonacci sequence is a special case of the more general family of Lucas sequences. Hence, the theory pertaining to the Lucas and companion Lucas sequences necessarily applies to the Fibonacci sequence.

That being said, the first place that $7$ divides the $F_{n}$ sequence is when $n = 8$. Hence, the "rank of apparition'' of $7$ in the $F_{n}$ sequence is $8$. That is, $\omega(7) = 8$. Moreover, for Lucas sequences, and thus for the Fibonacci sequence, a prime $p$ divides the Fibonacci sequence at a term, $F_{k}$ if and only if $k$ is some multiple of $\omega(p)$; that is, $p$ divides every term and only those terms of the said sequence whose index $k = m\omega(p),$ for every positive integer $m$. Hence, the only terms of the Fibonacci sequence that contain $7$ as a factor are

$$ F_{8}, F_{16}, F_{24}, \ldots.$$