The sum of $n$ consecutive Fibonacci numbers.

Question

The sum of $8$ consecutive Fibonacci numbers is divisible by $3$.

How can I generalize this for the sum of $n$ consecutive Fibonacci numbers? For example,

$$1+1+2+3+5+8+13+21=54=3\times 18 \\ 1+2+3+5+8+13+21+34=87=3\times 29 \\2+3+5+8+13+21+34+55=141=3\times 47$$

Answer 1

You want to find the $\gcd$ of the numbers

$$F_1+\cdots+F_n,\quad F_2+\cdots+F_{n+1},\quad F_3+\cdots+F_{n+2},\quad F_4+\cdots+F_{n+3},\quad \cdots\cdots$$

Since $F_1+\cdots+F_n=F_{n+2}-1 \implies F_{1+k}+\cdots+F_{n+k}=F_{n+k+2}-F_{k+2}$, this is

$$F_{n+2}-F_2,\quad F_{n+3}-F_3,\quad F_{n+4}-F_4,\quad F_{n+5}-F_5,\quad \cdots$$

Notice how this is a new Fibonacci(-like) sequence, in which each term is a sum of the two previous terms. Therefore, not only does the $\gcd$ of the whole sequence divide the $\gcd$ of the first two terms (this holds generically for any sequence), but the $\gcd$ of the first two terms divides all of the other terms hence divides the $\gcd$ of the whole sequence. Therefore, the $\gcd$ of the whole sequence is equal to the $\gcd$ of the first two terms! Using the algorithm $(a,b)=(a,b-a)$, we can simplify: $(F_{n+2}-F_2,F_{n+3}-F_3)=(F_{n+2}-F_2,F_{n+1}-F_1)=(F_n-F_0,F_{n+1}-F_1)$.

Therefore, the generalization of $3\mid(F_{k+1}+\cdots+F_{k+8})$ for all $k\ge0$ is

$$\gcd(F_n,F_{n+1}-1)\mid(F_{k+1}+\cdots+F_{k+n}).$$

Note this holds for negative values of $k$ too.

Answer 2

For every $m\in\mathbb{N}_{\geq 1}$, the Fibonacci sequence is periodic $\pmod{m}$, since there are at most $m^2$ couples of residue classes $(F_k,F_{k+1})\pmod{m}$. So there exist a number $\phi(m)\leq m^2$ (the Pisano period $\pmod{m}$) such that: $$ \forall n\in\mathbb{N},\quad F_{n}\equiv F_{n+\phi(m)}\pmod{m}. $$ Since it is easy to prove by induction that: $$ F_1 + F_2 + \ldots + F_{k} = F_{k+2}-1, $$ then the sum of $\phi(m)$ consecutive Fibonacci numbers is always divisible by $m$:

$$ F_{j+1} + \ldots + F_{j+\phi(m)} = F_{j+2+\phi(m)}-F_{j+2} \equiv 0\pmod{m}.$$