9
$\begingroup$

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?

$\endgroup$
0
15
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Nice argument, thank you. Upvoted. $\endgroup$ – T. Amdeberhan Jan 9 at 14:56
13
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Nice argument, thank you. Upvoted. $\endgroup$ – T. Amdeberhan Jan 9 at 14:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.