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.

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|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 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
add comment

1 Answer

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|improve this answer
add comment

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.