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

1 Answer 1

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$
2
  • $\begingroup$ The Yufei Zhao reference in the OEIS entry is also worth a look. (+1) $\endgroup$ Apr 21, 2016 at 6:19
  • 1
    $\begingroup$ @BrianM.Scott: You're right! Thanks! $\endgroup$
    – epi163sqrt
    Apr 21, 2016 at 6:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .