This question is motivated by recent work of R P Stanley, [Theorems and conjectures on some rational generating functions](https://arxiv.org/abs/2101.02131). 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?
> 
> 
> 



Counting monomials in product polynomials: Part I
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.


