Counting monomials in product polynomials: Part I

Question

This question is motivated by recent work of R P Stanley, Theorems and conjectures on some rational generating functions. Consider the polynomials $$P_n(x)=\prod_{i=1}^{n-1}(1+x^{3^{i-1}}+x^{3^i}).$$ Define the sequence $a_n$ to count the number of monomials of $P_n(x)$. For example, \begin{align*} P_2(x)&=x^3 + x + 1 \qquad \qquad \qquad \qquad \qquad \qquad\qquad \,\,\implies \qquad a_2=3, \\ P_3(x)&=x^{12} + x^{10} + x^9 + x^6 + x^4 + 2x^3 + x + 1 \qquad \implies \qquad a_3=8. \end{align*} Recall the Fibonacci numbers $F_1=F_2=1$ and $F_{n+2}=F_{n+1}+F_n$.

QUESTION. Is it true that $a_n=F_{2n}$? How does "ternary expansion" relate to Fibonacci?

Answer 1

Yes, it is true. In other words, you ask whether $|X_n|=F_{2n}$ where $$X_n:=\sum_{i=1}^{n-1}\{0,3^{i-1},3^i\}.$$ We have $$X_n=X_{n-1}\cup Y_{n-1}\cup Z_{n-1},\quad (1)$$ where $Y_{n-1}=X_{n-1}+3^{n-1}$, $Z_{n-1}=X_{n-1}+3^n$. We have $(X_{n-1}\cup Y_{n-1})\cap Z_{n-1}=\emptyset$, since $\min Z_{n-1}=3^n>\max (X_{n-1}\cup Y_{n-1})=2\cdot 3^{n-1}+3^{n-2}+\ldots+3$. So, we have \begin{align*} |X_n|&=|Z_{n-1}|+|X_{n-1}\cup Y_{n-1}| \\ &=|Z_{n-1}|+|X_{n-1}|+|Y_{n-1}|-|X_{n-1}\cap Y_{n-1}| \\ &=3|X_{n-1}|-|X_{n-1}\cap Y_{n-1}|\\ &=3|X_{n-1}|-|X_{n-2}| \end{align*} (that follows from the decomposition (1) with $n-1$ instead $n$: $X_{n-1}\cap Y_{n-1}=Z_{n-2}$).

That's the recursion for $F_{2n}$'s.

Answer 2

Here is another argument. We have $$ P_{n+1}(x)=(1+x+x^3)P_n(x^3). $$ Now $P_n(x^3), xP_n(x^3)$, and $x^3P_n(x^3)$ all have $a_n$ monomials. If a monomial $x^i$ appears in more than one of them, then it must appear in $P_n(x^3)$ and $x^3P_n(x^3)$, but not $xP_n(x^3)$ (by considering exponents mod 3). Thus we need to subtract off the number of monomials $x^i$ that appear in $P_n(x)$ such that $x^{i+1}$ also appears. By the uniqueness of the ternary expansion, the monomials with such $x^i$ or $x^{i+1}$ are those appearing in $(1+x)P_{n-1}(x^3)$. There are $2a_{n-1}$ such monomials, occurring in pairs $x^i$ and $x^{i+1}$. Hence $a_{n+1}=3a_n-a_{n-1}$, the recurrence satisfied by $F_{2n}$ (and with the correct initial conditions).