Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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 somewhere down that discussion has something like what you are looking for. – Kirthi Raman Mar 14 '12 at 15:25
up vote 1 down vote accepted

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.

share|cite|improve this answer

Your Answer


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.