Fibonacci sequence divisible by 7?

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$.

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.

Hint $ $ The shift map $\rm\:n\to n+1\:$ on pairs $\rm\:(f_{n-1},\:f_n)\,\ \ (mod\ 7)\,$ is an invertible map on a finite set, so is a permutation, so its orbits are cycles. 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 $\rm\,f(n+2) = f(n+1)^2 - f(n),\,$ with $\rm \,f(1) = 39\,$ and $\rm \,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).