# The sum of $n$ consecutive Fibonacci numbers.

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

-
See the accepted answer here math.stackexchange.com/questions/765104/… – Andreas Caranti Jun 13 '14 at 19:39
Fibonacci mod 3 are 1,1,2,0,2,2,1,0 periodic... – Peter Franek Jun 13 '14 at 19:40
Why are people closing this question as a duplicate of the one linked in @Andreas comment? The OP's fact is about finding something that divides any sum of $n$ consecutive Fibonacci numbers, not merely in finding an explicit formula for the sum. – blue Jun 13 '14 at 20:37
I agree with @seaturtles, question should not be closed. Sorry if my comment, which was just meant as a starting point, gave a false impression. – Andreas Caranti Jun 13 '14 at 21:00

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.

-
Sea Turtles, you might have a thing or two to teach them at the OEIS, like a simpler way to have Maple compute this. See oeis.org/A210209 – Robert Soupe Jun 14 '14 at 3:01

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

-