Fibonacci Game Invariant Sum

Question

The Problem

Suppose I start with two natural numbers, $F_1=x \pmod 7$ and $F_2=y \pmod 7$ so that not both $x$ and $y$ are $0$ (and of course, $x,y<7$). From there, I form the sequence $F_{n+1}=F_n+F_{n-1}\pmod 7$.

The interesting fact I noticed is that $\sum _1 ^{16} F_n=49$ always!

For example, if I started with, say $x=1$ and $y=4$, the first $16$ terms of my sequence would be $1,4,5,2,0,2,2,4,6,3,2,5,0,5,5,3$, and indeed, the sum is $49$.

Why is this?

What I've Tried

We note that if we expand the first $16$ terms generally, as functions of $x$ and $y$, that $F_a+F_{8+a}\equiv 0 \pmod 7$ for all $1\le a \le 8$ regardless of what $x$ and $y$ are. Since $F_a+F_{8+a}$ can only take on values of $0$ and $7$, it is enough to show that of the first $8$ numbers $F_1$ through $F_8$, exactly one has to be $0$ (the rest being nonzero would show that the total sum is always 7*7+0*1=49). Of course, we could brute force, but is there a nice way to see what's going on?

Answer 1

Because there only a limited number of possible pair values $\bmod 7$, and because given a certain pair you can work both forwards and backwards uniquely under Fibonacci rules, it is inevitable that you have cycles of values that return to their starting pair. I think there might be an element of small-number effect that the $48$ possible value pairs (since we exclude $0,0$) fall neatly into just $3$ cycles of length $16$, all including zeroes: $$\begin{array}{c} 0 & 1 & 1 & 2 & 3 & 5 & 1 & 6 & 0 & 6 & 6 & 5 & 4 & 2 & 6 & 1 & (0) \\ 0 & 2 & 2 & 4 & 6 & 3 & 2 & 5 & 0 & 5 & 5 & 3 & 1 & 4 & 5 & 2 & (0) \\ 0 & 3 & 3 & 6 & 2 & 1 & 3 & 4 & 0 & 4 & 4 & 1 & 5 & 6 & 4 & 3 & (0) \\ \end{array}$$

So every starting pair can be found in these cycles, which exhibit your symmetric effect of having $a_i\equiv -a_{i+8}$ (which also perpetuates through the Fibonacci recurrence).

So I don't know if that counts as a "nice way" - I certainly think there is more structure to be understood - but this is an interesting area that I was also looking at across bases (although I hadn't yet looked at variant starting values).

Answer 2

One way to prove your simplification (nice job btw!) [Not sure if this is nice enough, but it should be a little more satisfying than brute force]: Consider the group $G:=<A^2>\subset GL(2,\mathbb{F}_7)$ where $A=\begin{pmatrix}0&1\\1&1\end{pmatrix}$. Note that $A^2 \begin{pmatrix}F_n\\F_{n+1}\end{pmatrix} = \begin{pmatrix} F_{n+2}\\ F_{n+3}\end{pmatrix}$ (mod $7$) for all $n\in \mathbb{N}$. Computing powers of $A$ mod $7$: $A^2= \begin{pmatrix}1&1\\1&2\end{pmatrix}$, $A^4 = \begin{pmatrix} 2&3\\3&5\end{pmatrix}$, $A^8 = -I$. Thus $A$ has order $16$ and $|G|=8$.

Let $G$ operate on $\mathbb{F}_7^2$ by multiplication mod $7$. It is easy to see that every element $(0,0)\neq (a,b)\in\mathbb{F}_7^2$ is only fixed by the identity element of $G$. So its orbit has $8$ elements, and since $|\mathbb{F}_7^2| = 49 = 8\cdot 6 + 1$, there are $6$ of these in total. Let's consider the case that some orbit contains an element of type $(0,a)$ or $(a,0)$. The Fibonacci sequences starting at these points mod $7$ look like this:

$0,a,a,2a,3a,5a,a,-a,0,-a,..$

$a,0,a,a,2a,3a,5a,a,-a,0,..$

where the dots indicate that the same sequence as before is repeated with just $a$ exchanged for $-a$. So the orbits (excluding the trivial one) of pairs in $\mathbb{F}_7^2$ ,which contain a zero in one of their pairs, contain exactly 2 zeroes (in two of their pairs). Since there are (excluding the pair $(0,0)$) exactly $6\cdot 2 = 12$ of these, each of the $6$ orbits contains exactly two of them, with the 'distance' (in the Fibonacci sequence) of one zero to the next being $8$ (following from the expansion of the sequence above). So any $8$ consecutive numbers in a Fibonacci sequence contain exactly one that is divisible by $7$.

Answer 3

Funnily enough this happens for all $p$ in the sequence A000057, this sequence consists of primes $p$ for which the Fibonacci entry point is $p+1$ (i.e. the first positive $n$ for which $p$ divides $F(n)$ is $p+1$, where $(F(n))_{n \geq 0}$ is the Fibonacci sequence). Note that for all $p$ in this list the polynomial $x^2 - x - 1$ is irreducible in $\mathbb{F} _p[x]$ as is explained in section 4 of these notes.

The Conjecture

Take a prime number $p$ in A000057. The first few of these primes are $$2,\ 3,\ 7,\ 23,\ 43,\ 67,\ 83,\ 103,\ 127, \ 163,\dots.$$ Now let $F_{a,b}(n)$ be a sequence in $\mathbb{F}_p$ defined by $$F_{a,b}(0) = a,\ F_{a,b}(1) = b \text{ and } F_{a,b}(n) + F_{a,b}(n+1) = F_{a,b}(n+2).$$ We let $r_{a,b}(n)$ be the unique element of $\{0, \dots, p-1\}$ such that $r_{a,b}(n) \equiv F_{a,b}(n) \pmod{p}$. If we, for example, write down the first couple of terms of the sequence $r_{0,1}(n)$ for $p = 7$ we get $$ 0,\ 1,\ 1,\ 2,\ 3,\ 5,\ 1,\ 6,\ 0,\ 6,\ 6,\ 5,\ 4,\ 2,\ 6,\ 1,\dots $$ if we calculate the sum of these $16$ values we get $49$. We can try this a couple of more times for different values of $p$ and come to the conjecture that if $a,b$ are not both zero we find that $$\sum_{n=0}^{2p+1} r_{a,b}(n) = p^2.$$

The Proof

First we observe that $F_{a,b}(n) + F_{a,b}(n + p + 1)$ seems to be zero for all starting values $a,b$ and all $n$. To prove this we use the theory of characteristic polynomials for recurrence relations to obtain a general formula for the value of $F_{a,b}(n)$. The characteristic polynomial for this relation is given by $f(x) = x^2 - x - 1$. Since we have chosen $p$ such that $f(x)$ is irreducible in $\mathbb{F}_p[x]$ we have to go to the extension field $$\mathbb{F}_{p^2}:= \mathbb{F}_p[x]/(f(x))$$ to obtain the roots $z_1,z_2$ such that $f(x) = (x-z_1) (x-z_2)$. By comparing coefficients we see that $z_1 \cdot z_2 = -1$ and from the theory of finite fields we know that the Frobenius map $x \mapsto x^p$ sends $z_1$ to $z_2$ and vice versa. Now the general term $F_{a,b}(n)$ is given by $$F_{a,b}(n) = c_1 \cdot z_1^n + c_2 \cdot z_2^n,$$ where $c_1,c_2$ are constants in $\mathbb{F}_{p^2}$ that depend on the starting values $a,b$. We can now calculate that

\begin{align*} F_{a,b}(n+p+1) &= c_1\cdot z_1^{n+p+1} + c_2 \cdot {z_2}^{n+p+1} \\ &= c_1 \cdot z_1^n \cdot z_1 \cdot z_1^p + c_2 \cdot {z_2}^n \cdot {z_2} \cdot {z_2}^p \\ &= c_1 \cdot z_1^n \cdot (z_1 \cdot {z_2}) + c_2 \cdot {z_2}^n \cdot ({z_2} \cdot z_1) \\ &= - c_1 \cdot z_1^n - c_2 \cdot {{z_2}}^{n}\\ &= -F_{a,b}(n). \end{align*}

This tells us that indeed $F_{a,b}(n) + F_{a,b}(n + p + 1) = 0$. Let us now consider the sequences of the form $F_{0,a}(n)$, such that the first value is zero. We see that $c_1 = -c_2$ such that the general formula is of the form $$F_{0,a}(n) = C(z_1^n - z_2^n),$$ where $C \in \mathbb{F}_{p^2}$ depends on $a$. We want to know when $F_{0,a}(n) = 0$ for the first time with $n > 0$ for non-zero $a$. Looking at the direct formula we see that $F_{0,a}(n) = 0$ if and only if $z_1^n = z_2^n$. From Galois theory we know that this happens if and only if $z_1^n \in \mathbb{F}_{p}$. Now using the fact that $z_1^2 = z_1 +1$ we can prove by induction that $$z_1^n = \overline{F (n)} \cdot z_1 + \overline{F(n-1)},$$ where $(F(n))_{n \geq 0}$ is now the regular Fibonacci sequence. So we see that this is an element of $\mathbb{F}_{p}$ if and only if $F(n)$ is divisible by $p$. So we are looking for the first positive $n$ such that $F(n)$ is divisible by $p$. We have chosen $p$ precisely such that this value is $p+1$. This means that the period of $F_{0,a}$ is at least $p+1$, but since $F_{0,a}(1) = a$ and $F_{0,a}(p+2) = -a$ and these are not equal, we see that the period of $F_{0,a}$ is $2(p+1)$. So we see that the pairs $$ (F_{0,a}(0),F_{0,a}(1)),\ (F_{0,a}(1),F_{0,a}(2)),\ \dots, \ (F_{0,a}(2p+1),F_{0,a}(2p+2)) $$ are all different. We also see that the sequences $$F_{0,1},\ F_{0,2}, \dots, F_{0,\frac{p-1}{2}}$$ are all different since a sequence of the form $F_{0,a}$ contains only the two tuples $(0,a)$ and $(0,-a)$ with $0$ as the first entry of the pair. So if we now count pairs we have found $$\frac{p-1}{2}\cdot 2(p+1) = p^2-1,$$ together with the trivial sequence $F_{0,0}$ we see that we have counted all $p^2$ pairs and thus all sequences $F_{a,b}$ are actually of the form $F_{0,c}$ for some $c$ possibly shifted. Since the period of $F_{a,b}$ is $2(p+1)$ the sum is constant under the shifting of the sequence such that $$\sum_{n=0}^{2p+1} r_{a,b}(n) = \sum_{n=0}^{2p+1} r_{0,c}(n),$$ for some $c$. We have seen that if $c \neq 0$ indeed $0$ only appears two times in the sum. Since $F_{a,b}(n+p+1)=-F_{a,b}(n)$ we see that $r_{a,b}(n+p+1)+ r_{a,b}(n) = p$ if $F_{a,b}(n) \neq 0$ and thus we see that the sum is equal to $$\sum_{n=0}^{2p+1} r_{0,c}(n) = p^2.$$