Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
See the accepted answer here math.stackexchange.com/questions/765104/… –  Andreas Caranti Jun 13 at 19:39
4  
Fibonacci mod 3 are 1,1,2,0,2,2,1,0 periodic... –  Peter Franek Jun 13 at 19:40
1  
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 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 at 21:00

2 Answers 2

up vote 6 down vote accepted

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.

share|improve this answer
2  
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 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}.$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.