3
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ See the accepted answer here math.stackexchange.com/questions/765104/… $\endgroup$ Jun 13 '14 at 19:39
  • 4
    $\begingroup$ Fibonacci mod 3 are 1,1,2,0,2,2,1,0 periodic... $\endgroup$ Jun 13 '14 at 19:40
  • 1
    $\begingroup$ 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. $\endgroup$
    – blue
    Jun 13 '14 at 20:37
  • $\begingroup$ 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. $\endgroup$ Jun 13 '14 at 21:00
6
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ 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 $\endgroup$ Jun 14 '14 at 3:01
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy