# Fibonacci sequence divisible by 7?

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.

-
Write down the first 30 fibonacci numbers, check which ones are divisible by 7, and tell us what you conjecture. No one is going to make a conjecture for you. –  Zev Chonoles Apr 23 '11 at 21:17
@Bill Dubuque Re homework questions, the relevant thread meta.math.stackexchange.com/questions/1803/… says (extract): please put some work into formulating your question. Please do not just copy and paste the exact question text from your homework sheet. In particular, when you are asking for help, writing in imperative mode ("Show that...", "Compute...", or "Prove or find a counterexample: ...") is at the very least impolite: you are, after all, trying to ask a question, not give an assignment. It also turns many people off. So it seems that .../... –  Did Apr 23 '11 at 22:17
.../... the source of a question is indeed irrelevant but, despite the agenda you seem to push forward, not its formatting. Later on, the same thread says: Show your work. You should definitely include any partial work you have done. This will help bolster your claim that you are not just coming here asking other people to do your homework for you. I wonder how you would rate the question at hand with respect to these criteria. –  Did Apr 23 '11 at 22:17
@Bill: The point of the meta post I linked to is the discrepancy between the few accepted rules on this site and your interpretation of how people should behave here. You are entitled to your opinions about this, as everyone else, but I suggest you stop presenting these as the official truth and the one and only morally acceptable modus operandi. This is pure intimidation. –  Did Apr 23 '11 at 22:36
I think we should work together on this site to make it fun and helpful rather than fighting. –  quanta Apr 23 '11 at 23:49

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

-
It's the right observation but there's no proof here. –  lhf Apr 24 '11 at 1:47
I'd be happier with an induction but I see now that you've listed the whole sequence mod 7 until a cycle appears, so it's ok. –  lhf Apr 24 '11 at 11:31
@quanta: As it's written, I wouldn't call it a rigorous proof (in a homework assignment, I wouldn't give full points), but if I was talking to a college, I wouldn't want him to tell me more, so in this sense it's indeed complete. –  Hendrik Vogt Apr 24 '11 at 12:51
@quanta: Because you didn't explicitly write why it repeats forever. I'm pretty sure you fully understand what you're writing in your answer, and I gave you +1 for it since it's the easiest (and hence best) answer here, but I can't look into your mind and see if you really understand everything: If you were a student of mine whom I don't know well, I'd subtract a point; if you were a studied mathematician, I'd expect exactly the answer you gave above and no more. –  Hendrik Vogt Apr 24 '11 at 13:02
@quanta: Wow, I certainly didn't expect you to fill so many details. As for your last comment, I'm thinking both as a researcher and a scientist. As a researcher, I was perfectly happy with your original answer (so I upvoted it since I thought "ah, that makes is clear", not "this is a rigorous proof"), but I wanted to point out that someone who just starts learning these things really shouldn't think that this was a complete rigorous proof. The meaning of "complete rigorous" of course depends very much on your level of knowledge. –  Hendrik Vogt Apr 24 '11 at 18:25

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.

-
Alternatelly one can use the $F$ matrix $(1 1 \\ 1 0)$ and check it's 8'th power. The first row gives your relation, anyhow the entire matrix is $(f_8 f_7 \\ f_7 f_6)$ which mod 7 is $(-1 0 \\ 0 1 )$. –  N. S. Apr 24 '11 at 17:58
@user9176 Note that your matrix is simply the matrix form of the shift map mentioned in my answer. Here linearity is in fact irrelevant. All that matters is that the shift map is invertible, so a permutation, so its orbits are cycles; e.g. see the nonlinear recursion in my answer. –  Bill Dubuque Apr 25 '11 at 2:01

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

-
Wouldn't you also need to prove that $F^{\text{something}}(39,45) = (39,45)$? –  quanta Apr 23 '11 at 23:27
@quanta Since $\rm\:F\:$ is permutation its orbits are cycles. That's the key point. In that sci.math thread other folks where proving this from scratch "reinventing the wheel (cycle)". –  Bill Dubuque Apr 23 '11 at 23:39
How is it seen that F is a permutation? –  quanta Apr 23 '11 at 23:48
@quanta: Hint: it's an invertible map on a finite set - see the sentence that begins "Simpler". –  Bill Dubuque Apr 24 '11 at 0:44