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.