3
$\begingroup$

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).

  • 0
    There are two answers already referring to Zeckendorf's system, but I am not sure if this helps or not check http://www1.math.american.edu/People/kalman/pdffiles/fibpaper.pdf somewhere down that discussion has something like what you are looking for.2012-03-14

1 Answers 1

1

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.