Fibonacci
Representation of numbers (end)
If each number can be written as a sum of different Fibonacci numbers, then we may ask for
the number of ways in which a numbers a may be represented.
Let us denote this number by m(a).
Suppose k and n are positive integers and k<Fn.
We will investigate the representations of a = Fn+2 - k.
First we look at those representations in which the term Fn+1 is absent. We know, that
F1 + F2 + F3 + ... + Fn = Fn+2 - 1, (***)
so we find all representations without the term Fn+1 by
summing up all representations of k-1, followed by subtracting the terms in these representations from (***).
Now we are left with those representations containing a term Fn+1. Then a = Fn+1 + Fn - k.
So, this number is m(Fn - k).
In short: m(Fn+2 - k) = m(k-1) + m(Fn - k)
The formula is also correct for k=0 if we define m(-1)=1.
If we know m(i) for i between Fn and Fn+1 then the derived recursion yields
all values for m(i) with i between Fn+1 and Fn+2.
Furthermore (without proof) m(Fn+2 - k) = m(Fn+1 + k - 1) for 0 < k <= Fn
To calculate m(i) we may use the formula
(1 + x F1 ) (1 + x F2 ) ... (1 + x Fr ) = 1 + m(1)x + m(2)x2 + ... + m(Fr+1-1)xFr+1-1 +
(m(Fr+1) - m(1))xFr+1 +
(m(Fr+1+1) - m(2))xFr+1+1 +
(m(Fr+2-1) - m(Fr))xFr+2-1
If you are able to derive other relations between the m(i)'s, let me know.
In conclusion we ask ourselves whether there exists a number z such, that each positive integer can be written as a sum of
at most z different Fibonacci numbers.
Well, F1 + F2 + F3 + ... + F2n-2 = F2n - 1
The number of terms for F2n - 1 may only be reduced by using the term F2n-1. Then
F2n - 1 = F2n-1 + (F2n-2 - 1). For F2n-2 - 1 the same story applies.
Thus, the minimal representation for F2n - 1 is F2n-1 + F2n-3 + ... + F3.
The number of terms increases with n.