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?

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