7
$\begingroup$

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

$\endgroup$
6
  • 9
    $\begingroup$ It should be possible to obtain an answer using arxiv.org/pdf/math/0409418.pdf. $\endgroup$ Commented Mar 30, 2017 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$ Commented Mar 30, 2017 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$ Commented Mar 30, 2017 at 23:59
  • 2
    $\begingroup$ @Richard Stanley There are 2 more links at oeis.org/A151661 $\endgroup$ Commented Mar 31, 2017 at 6:29
  • 1
    $\begingroup$ @RichardStanley: That was a useful paper to refer to, thanks! $\endgroup$ Commented Mar 31, 2017 at 21:22

3 Answers 3

4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
0
$\begingroup$

The results with generating functions also suggest that a "closed formula" for $N(P_n)$ can be written as: $$N(P_n)=br^n+cs^n+dt^n$$ where $b,c,d$ and $r,s,t$ are the roots of \begin{align} a^3-2a^2+2a-2 &= 0\\ 22q^3-22q^2+2q-1 &= 0 \end{align} whose imaginary parts are respectively zero, positive, and negative.

This is the result of solving for $b,c,d$ that make the first three terms work, and works at least for $2\le n\le 20$.

For $2\le n \le 45$ this gives the sequence $$2, 4, 6, 8, 12, 20, 32, 48, 72, 112, 176, 272, 416, 640, 992, 1536, 2368, 3648, 5632, 8704, 13440, 20736, 32000, 49408, 76288, 117760, 181760, 280576, 433152, 668672, 1032192, 1593344, 2459648, 3796992, 5861376, 9048064, 13967360, 21561344, 33284096, 51380224, 79314944, 122437632, 189005824, 291766272.$$

$\endgroup$

You must log in to answer this question.

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