# Counting monomials in product polynomials: Part I

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?

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