# Sums of Fibonacci numbers

Given a multiset S of integers, when is $$\sum_{s\in S}F_{n+s}=kF_{n+t}$$ for some integers k and t and all integers n? $F_n$ is the n-th Fibonacci number.

Essentially, given a sum of Fibonacci numbers with fixed offsets, when can it be simplified to a multiple of a single Fibonacci number? (Example: $F_{n-1}+2F_{n}+F_{n+2}=2F_{n+2}.$)

The generalization $$\sum_{s\in S}F_{n+s}=k_1F_{n+t_1}+k_2F_{n+t_2}$$ is also of interest to me, if there is a nice N&S condition for it. And of course generalizations in other directions (any linear recurrence?) might be useful (though the special case of Fibonacci numbers is of special interest).

-
Highly relevant: Zeckendorf family identities generalized. – anon Mar 14 '12 at 15:09
Try looking at Zeckendorf's system, maybe it will help. – dtldarek Mar 14 '12 at 15:15
There are two answers already referring to Zeckendorf's system, but I am not sure if this helps or not check www1.math.american.edu/People/kalman/pdffiles/fibpaper.pdf somewhere down that discussion has something like what you are looking for. – Kirthi Raman Mar 14 '12 at 15:25

I'll consider the case where $k$ is rational. Define the polynomial $$P(X)=\sum_{s\in S} X^s$$ and $$Q = P = aX+b \pmod{X^2-X-1}$$ Then if $$\sum_{s\in S} F_{n+s}=k F_{n+t}$$ we have $$Q = kX^t \pmod{X^2-X-1}$$ $$Q = kF_{t+1} X+kF_t \pmod{X^2-X-1}$$ so $a/b$ is the ratio $F_{t+1}/F_t$.
Conversely if $a/b$ can be expressed as $F_{t+1}/F_t$ for some integer $t$, define $k=b/F_t$. Then the equation is satisfied. It's easy to see that $k$ and $t$ are unique.
The restriction to integer $k$ then follows, by checking whether $F_t$ divides $b$.
The generalization is trivially satisfied for all $P$ by taking $k_1=b$, $t_1=0$, $k_2=a$, $t_2=1$.
This is not specific to the Fibonacci sequence, any linear recurrence will do. Informally what the polynomial modulo $X^2-X-1$ represents is the "state" of the sequence. So if $Q$ transforms the state exactly like going forward $t$ steps would do, the sum will coincide with a translated sequence.