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$.

  • 9
    $\begingroup$ It should be possible to obtain an answer using arxiv.org/pdf/math/0409418.pdf. $\endgroup$ – Richard Stanley Mar 30 '17 at 13:27
  • 5
    $\begingroup$ If we set $N(P_0) = N(P_1) = 1$, then experimentally it seems the sequence $N(P_n)$ has the rational generating function $f = \displaystyle\frac{1-z+2z^2}{1-2z+2z^2-2z^3}$. $\endgroup$ – Jay Pantone Mar 30 '17 at 14:07
  • $\begingroup$ Unless I'm mistaken, the related product $\Pi_k(1+x^{F_k})$ will always have exactly all the terms $\leq F_{n+2}-2$ by a version of the Zeckendorff theorem, so the issue is understanding when terms cancel perfectly, correct? (Loosely similar to the Pentagonal number theorem) (ETA: and I see that's exactly what the paper pointed to by Mr. Stanley's comment does...) $\endgroup$ – Steven Stadnicki Mar 30 '17 at 23:59
  • 2
    $\begingroup$ @Richard Stanley There are 2 more links at oeis.org/A151661 $\endgroup$ – Alexey Ustinov Mar 31 '17 at 6:29
  • 1
    $\begingroup$ @RichardStanley: That was a useful paper to refer to, thanks! $\endgroup$ – T. Amdeberhan Mar 31 '17 at 21:22

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, 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 3,4\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.


Thanks to Stanley for this paper by Ardila, we are able to confirm Pantone's generating function.

One useful fact used below is $$F_1+F_2+\cdots +F_n=F_{n+2}-1.\tag1$$ In the aforementioned work by Ardila, the block-splitting of the coefficients $a_k$, in the infinite product $$\prod_{n\geq 2}(1-x^{F_n})=\sum_{k\geq 0}a_kx^k,$$ allows indicies in $[F_n,F_{n+1}-1]$ to be broken up into three subintervals $[F_n,F_n+F_{n-3}-2], [F_n+F_{n-3}-1,F_n+F_{n-2}-1]$ and $[F_n+F_{n-2},F_{n+1}-1]$. This is followed by a $3$-block comparison of coefficients. The good news is that although our focus is in the partial products $$P_n(x)=\prod_{k=2}^n(1-x^{F_k})=\sum_{j=0}^{F_{n+2}-2}q_jx^j,\qquad n\geq 2,$$ ($q_j$ and $a_j$ are generally unequal), however Ardela's description for $a_j$ continues to hold for $q_j$. We invoke the result as such.

Corollary. We've the generating function for $N(P_n(x))$; namely, $$\sum_{n\geq 2}N(P_n(x))z^n=\frac{2z^2(1+z^2)}{1-2z+2z^2-2z^3}.$$ \rm \bf Proof. \rm The critical step is: if $b_n=N(P_n(x))$ and $Eb_n=b_{n+1}$ then $(E^3-2E^2+2E-2)b_n=0$. In fact, we prove that $(E^4-E^3-2)b_n=0$ or $$b_{n-1}=b_{n-2}+2b_{n-5}.\tag2$$ Note: $E^4-E^3-2=(E+1)(E^3-2E^2+2E-2)$.

From (1), it follows that $P_{n-1}(x)$ has degree $F_{n+1}-2$. According to Ardela's characterization (modified to exclude $q_{F_{n+1}-1}$ and hence $q_{F_{n-3}-1})$ we have the two non-zero blocks, of the three, carrying the same number of terms, that is $N(P_{n-5}(x))=b_{n-5}$. The remaining interval $[0,F_n-1]$ simply goes to count $N(R_{n-2}(x))$. Hence $$N(P_{n-1}(x))=N(P_{n-2}(x))+2N(P_{n-5}(x))$$ completes our verification of (2). At this point use initial conditions to write the generating function $$\frac{2z^2(1+z+z^2+z^3)}{1-z-2z^4}=\frac{2z^2(1+z^2)}{1-2z+2z^2-2z^3}.$$


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.