Number of ways to write $n$ as sum of odd or even number of Fibonacci numbers

Question

In our discrete mathematics exercises I came of with the question:

Prove that the coefficients of $\prod_{n\geq2}{(1-x^{F_n})}=1-x-x^2+x^4+x^7+\dots$ can only be $-1,1$ or $0$, where $F_n$ denotes the n'th fibonacci number.

If we want to find the coefficient of $x^n$, we should choose some distinct terms from the products so that $n$ is written as sum of some fibonacci numbers , and because each term is in the form of $(1-x^{F_n})$, if we choose an odd number of them we will have $-1$ and if we choose an even number of them we will have $+1$.

So the question is the same as:

Prove that the number of ways to write a natural number as sum of odd number of fibonacci numbers differs at most $1$ number from number of ways of writing it as sum of even number of fibonacci numbers

(Note that the noted fibonacci numbers start from $F_2$)
My approach using induction is as follows:

Assume the proposition is true for all values of $n<k$, we shall prove it for $n=k$.
First note that for every number $k$ there exists $m$ so that $F_m\leq k < F_{m+1}$. We take $A=k-F_m$. Obviously $A<k$ so by induction hypothesis the proposition is true for $A$.There are two different possibilities for $A$:
1) $A<F_{m-2}$
In this case we have $k=F_m+A=F_{m-1}+F_{m-2}+A$. Note that because $A<F_{m-2}$, we have a one to one correspondence between the odd ways and the even ways and so the difference will stay $+1,0,-1$ depending on $A$
2) $A\geq F_{m-2}$
I'm actually stuck here and I cant find a similar proof for this case. I'd appreciate any help.

Answer 1

The following papers provide a proof of OPs claim:

• Federico Ardila presents in The Coefficients of a Fibonacci Power Series a clever subdivision of the interval $$[F_n,F_{n+1})$$ into three parts and proves that consecutive intervals have essentially the same shape. Then a rather simple induction proof can be used to finalize the claim.

• Neville Robbins Fibonacci Partitions provided a different proof some years earlier.

It could be interesting to note, that these proofs do not refer to the Zeckendorf representation of natural numbers as unique sum of different, non-consecutive Fibonacci numbers.

The coefficients of this product $$\prod_{n\geq 2}\left(1-x^{F_n}\right)$$ can be found in OEIS as A093996.