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.

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