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

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.

• You wrote $(1-x)^{F_n}$ once and $(1-x^{F_n})$ once -- which one do you mean? – joriki Apr 7 '16 at 9:04
• The second one! Thanks for noting, i edited the question. – CODE Apr 7 '16 at 9:10
• I don't quite understand your argument in case 1). The issue is that not every representation of $k$ is obtained from one of your $A$. E.g. when $k=14$, $A=1$ has only one such representation. But $14=13+1=8+5+1=8+3+2+1$. – Stephen Apr 8 '16 at 19:25

• 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.
The coefficients of this product $$\prod_{n\geq 2}\left(1-x^{F_n}\right)$$ can be found in OEIS as A093996.