Let $F\_i$ denote the $i$th Fibonacci number (with $F\_1=F\_2=1$). Define
$$ P\_n(x) = \prod\_{i=1}^n (1+x^{F\_{i+1}}). $$
Let $\nu\_k(n)$ denote the number of coefficients of the polynomial $P\_n(x)$
that are equal to the positive integer $k$. Evidence suggests that for
sufficiently large $n$ (depending on $k$), $\nu\_k(n)$ is a linear
polynomial in $n$. These polynomials for $1\leq k\leq 12$ are
empirically given by $2n$, $4n-8$, $8n-32$, $12n-68$, $16n-112$,
$24n-192$, $24n-224$, $36n-352$, $40n-432$, $48n-544$, $40n-512$, and
$88n-1056$. How can one prove these observations and generalize to any
$k$? Similar conjectures can be made for a wide class of more
general polynomials. See my papers <https://arxiv.org/abs/1901.04647>
and <https://arxiv.org/abs/2101.02131> for some related results. The
linear algebraic techniques in these papers might be applicable to
the present problem.


**Addendum.** The case $k=1$ follows easily from properties of the Fibonacci triangle poset discussed in Section 3 of <https://arxiv.org/abs/2101.02131>.



Number of coefficients equal to $k$ in certain "Fibonacci polynomials"
I will use the set up of [my answer](https://mathoverflow.net/q/266215) to a previous question about "Fibonacci polynomials".


The key observation is that the coefficient of $x^m$ in $P(x)$ equals the number of "unrollings" of the Zeckendorf representation $Z\_m$ (viewed as a $01$-string) of $m$, where any substring $001$ can be unrolled into $110$. Let $U(Z\_m)$ denote the number of such unrollings. It is easy to see that
$$U(0^p1v) = U(v) + \left\lfloor\frac{p}2\right\rfloor U(0v).$$


Then one can notice that
$$\nu\_k(n) = \nu'\_k(n) + \nu'\_k(n-1) - [k=1],$$ where $\nu'\_k(n)$ is the number of coefficients of $x^m$ in $P(x)$ equal $k$ with $m<F\_{n+2}$ (ie. $|Z\_m|\leq n$). Here the [Iverson bracket](https://en.wikipedia.org/wiki/Iverson_bracket) $[k=1]$ eliminates double counting of $v=0^n$ and $v=0^{n-1}$, which both correspond to $m=0$ .


The aforementioned recurrence for $U$ allows us to obtain one for $\nu'\_k(n)$ as follows.


Let $a\_1(n,k)$ be the number of strings $v$ of length $n$ starting with 0 such that $U(v)=k$, and let $a\_2(n,k\_1,k\_2)$ be the number of strings $v$ of length $n$ starting with 0 such that $U(v)=k\_1$ and $U(0v)=k\_2$. Clearly, $a\_2(n,k\_1,k\_2)=0$ whenever $k\_1>k\_2$ and we find it convenient to assume that both $a\_1$ and $a\_2$ are zero for $n<0$. Then we have
$$\nu'\_k(n) = a\_1(n,k) + a\_1(n-1,k),$$
where the terms enumerate $v$ starting with 0 and 1, respectively. The count $a\_1$ satisfies the recurrence:
\begin{split}
a\_1(n,k) &= [k=1] + a\_1(n-2,k) \\
&+ \sum\_{p=2}^{2k-1} \sum\_{k\_2 = \lceil k/(1+c\_p)\rceil}^{\lfloor (k-1)/c\_p\rfloor} a\_2(n-1-p,k-c\_pk\_2,k\_2),
\end{split}
where $p$ runs over the possible lengths of the initial run of 0's in $v$, the first term corresponds to $v=0^n$ and the second term corresponds to $p=1$, and $c\_p:=\left\lfloor\frac{p}2\right\rfloor$. Finally, the count $a\_2$ satisfies the recurrence:
\begin{split}
&a\_2(n,k\_1,k\_2) = [(k\_1,k\_2)=(1,1)] \\
&+ [k\_1=k\_2]\cdot\sum\_{c=1}^{k\_1-1} \sum\_{t = \lceil k\_1/(1+c)\rceil}^{\lfloor (k\_1-1)/c\rfloor} a\_2(n-1-2c,k\_1-ct,t) \\
& + [k\_1<k\_2]\cdot a\_2(n-1-(2\lfloor \tfrac{k\_1-1}{k\_2-k\_1}\rfloor+1), (k\_1-1) \bmod (k\_2-k\_1) + 1,k\_2-k\_1),
\end{split}
where the terms correspond to $v=0^n$, even $p>0$, and odd $p>0$, respectively.




---


**Example $k=1$.** In this case we have $a(n,1) = 1 + a\_1(n-2,1)$, implying that $a\_1(n,1)=1+\left\lfloor\frac{n}2\right\rfloor$. Then $a\_2(n,0,1) = 0$ and $a\_2(n,1,1) = 1$. It follows that $\nu'\_1(n) = n+1$ and $\nu\_1(n) = 2n$.


**ADDED.** It can be seen that $a\_2(n,k\_1,k\_2)$ stabilizes as $n$ grows and its limit $\bar a\_2(k\_1,k\_2)$ satisfies the recurrence:
\begin{split}
&\bar a\_2(k\_1,k\_2) = [(k\_1,k\_2)=(1,1)] \\
&+ [k\_1=k\_2]\cdot \sum\_{c=1}^{k\_1-1} \sum\_{t = \lceil k\_1/(1+c)\rceil}^{\lfloor (k\_1-1)/c\rfloor} \bar a\_2(k\_1-ct,t) \\
& + 
[k\_1<k\_2]\cdot \bar a\_2( (k\_1-1) \bmod (k\_2-k\_1) + 1, k\_2-k\_1).
\end{split}
Then it is easy to find the coefficient $q\_k$ of $n$ in the linear formula for $\nu\_k(n)$ (which is the quadruple of such coefficient in $a\_1(n,k)$) as
$$q\_k = 2[k=1] + 4\sum\_{c=1}^{k-1} \sum\_{k\_2 = \lceil k/(1+c)\rceil}^{\lfloor (k-1)/c\rfloor} \bar a\_2(k-ck\_2,k\_2).$$
Here are the values of $q\_k$ for $k\leq 30$:



```
2, 4, 8, 12, 16, 24, 24, 36, 40, 48, 40, 88, 48, 72, 96, 108, 64, 152, 72, 176, 144, 120, 88, 312, 144, 144, 200, 264, 112, 416

```

There seems to be no easier way to get the free term of $\nu\_k(n)$ than computing it as $\nu\_k(n) - q\_kn$ for large enough $n$.


