9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You wrote $(1-x)^{F_n}$ once and $(1-x^{F_n})$ once -- which one do you mean? $\endgroup$ – joriki Apr 7 '16 at 9:04
  • $\begingroup$ The second one! Thanks for noting, i edited the question. $\endgroup$ – CODE Apr 7 '16 at 9:10
  • $\begingroup$ 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$. $\endgroup$ – Stephen Apr 8 '16 at 19:25
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The Yufei Zhao reference in the OEIS entry is also worth a look. (+1) $\endgroup$ – Brian M. Scott Apr 21 '16 at 6:19
  • 1
    $\begingroup$ @BrianM.Scott: You're right! Thanks! $\endgroup$ – Markus Scheuer Apr 21 '16 at 6:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.