Let $F\_n$ denote the all-familiar Fibonacci numbers, with $F\_0=0, F\_1=1, F\_2=1$, etc.


There is a plethora of properties for these numbers involving their sums, products, convolutions and so on. Here, we are concerned with expanding linear (polynomial) factors. Consider
$$P\_n(x):=\prod\_{k=2}^n(1-x^{F\_k}).$$



> 
> **Question.** What is a closed formula for the number of monomials, $N(P\_n)$, in the expansion of $P\_n(x)$?
> 
> 
> 


**Examples.** $P\_2(x)=-x+1, P\_3(x)=x^3-x^2-x+1$ and hence $N(P\_2)=2, N(P\_3)=4$. 



Expanding in Fibonacci powers
Here is the direct proof without using the result of Ardila.


We will represent a sum of distinct Fibonacci numbers $m=\sum\_{j=2}^n b\_{j-1} F\_j$, where $b\_j\in\{0,1\}$, as a bit string $b\_1b\_2\ldots b\_{n-1}$. In the case of [Zeckendorf's representation](https://en.wikipedia.org/wiki/Zeckendorf%27s_theorem), in the corresponding bit string every pair of 1s is interspaced with at least one 0.


We remark that an arbitrary bit string $s$ can be converted into Zeckendorf's representation by scanning $s$ from right to left and replacing *every* substring $110$ with $001$ (and start scanning from the right-most end again). This way an $(n-1)$-bit string may be turned into an $n$-bit string. Conversely, we can "unroll" Zeckendorf's representation into another sum of distinct Fibonacci numbers by scanning the string from left to right and replacing *some* substring $001$ with $110$ (and starting scanning from the left-most end again).


The coefficient $c\_m$ of $x^m$ in $P\_n(x)$ is the difference between $(n-1)$-bit representations of $m$ with even and odd number of 1s. Furthermore, $c\_m$ can be nonzero only if $m\leq F\_{n+2}-2$. To compute $c\_m$, we consider Zeckendorf's representation $Z\_m$ of $m$ in the form of $n$-bit string.


The general structure of $Z\_m$ is
$$Z\_m = 0^{p\_1} 1 0^{p\_2} \dots 0^{p\_t} 1 0^{p\_{t+1}},$$
where $t\geq 0$, $p\_1\geq 0$, $p\_{t+1}\geq 0$, $p\_i\geq 1$ for $1<i<t+1$. Let us compute $c\_m=c(Z\_m)$ by unrolling $Z\_m$ in all possible ways into $(n-1)$-bit strings. One can show that for any bit string $u$, we have
$$
c(0^p1u) = \begin{cases} c(u), & \text{if}\ p\equiv 0,1\pmod{4};\\
c(u) - c(0u), & \text{if}\ p\equiv 2,3\pmod{4}.\end{cases}
$$
In the latter case, all unrollings of $u$ cancel out, and we can claim that when $c(u) - c(0u)\ne 0$, we have $c(u) - c(0u) = \pm c(v)$, where the string $11v$ is obtained from $0u$ by telescopically unrolling left-most 1 in $0u$. Notice that $v$ starts with 0, $|v|=|u|-1$, and if $u$ is in Zeckendorf's form, then so is $v$.


We start with the case $p\_{t+1}\geq 1$. Every 1 in $Z\_m$ here may or may not be unrolled (possibly telescopically).
For $s=0,1$, let $f\_s(z)$ be the g.f. for the number of $n$-bit $Z\_m$ such that $p\_1\geq s$, $p\_{t+1}\geq 1$, and $c(Z\_m)\ne 0$. From the above analysis, it follows that
$$f\_1(z) = \frac{z}{1-z} + \frac{z^4+z}{1-z^4}zf\_1(z) + \frac{z^2+z^3}{1-z^4}z^2\left(f\_1(z)-\frac{z}{1-z^2}\right).$$
The first term in the r.h.s. here accounts for strings of all zeros, while the second and third cases deal with strings $0^p1u$ with $p\equiv 0,1\pmod{4}$ and $p\equiv 2,3\pmod{4}$, respectively. Subtraction of $\frac{z}{1-z^2}$ is needed, since the resulting $v$ here cannot have the form $(01)^k0$ (which would imply $p\_{t+1}=0$). Solving the linear equation w.r.t. $f\_1(z)$, we get:
$$f\_1(z) = \frac{z-2z^5}{1-z-z^2+z^3-2z^4+2z^6}.$$
Correspondingly, we have
$$f\_0(z) = 1 + (1+z)f\_1(z) = \frac{1-z+z^2-2z^4}{1-2z+z^2-2z^4+2z^5}.$$


In the case of $p\_{t+1}=0$, the right-most ($n$-th) bit in $Z\_m$ must be unrolled and only such representations are taken into account. Let us similarly define generating functions $g\_s(z)$ (for $s=0,1$) addressing this case. Then
$$g\_1(z) = \frac{1+z}{1-z^4}z^3 + \frac{z^4+z}{1-z^4}zg\_1(z) + \frac{z^2+z^3}{1-z^4}z^2\left(g\_1(z)+\frac{z}{1-z^2}\right).$$
The terms meaning here is the same as before, except that the first term now accounts for the strings of form $0^{n-1}1$ (which has to be unrolled into $0^{n-3}110$), while addition of $\frac{z}{1-z^2}$ in the parentheses accounts for $v$ of the form $(01)^k0$ (i.e., with zero last bit) which results from $u=0^{2k+1}1$.
Solving for $g\_1(z)$, we get
$$g\_1(z) = \frac{z^3}{1-z-z^2+z^3-2z^4+2z^6}$$
and correspondingly
$$g\_0(z) = (1+z)g\_1(z) = \frac{z^3}{1-2z+z^2-2z^4+2z^5}.$$


Summing up the two cases, we get the g.f. for the number of $m$ with nonzero $c\_m$:
$$f\_0(z) + g\_0(z) = \frac{1-z+2z^2}{1-2z+2z^2-2z^3},$$
which confirms the conjecture of Jay Pantone.


