# Prove the coefficients of $\prod_{k=2}^{n+1}(1-x^{a_k})$ are $0$, $1$, or $-1$ where $(a_k)$ are Fibonacci numbers.

Given $$a_1 =1,a_2=1, a_{n+2}=a_{n+1}+a_n$$, prove that for $$n\geq 2$$, all coefficients of polynomial $$A(x)=\prod_{k=2}^{n+1}(1-x^{a_{k}})$$ are $$0$$, $$1$$, or $$-1$$.

I tried induction. I don't think it works. The hypothesis will be too weak. I think if we want to prove it by induction, we need to prove a stronger proposition, but I can't find it.

• What do you mean by "coefficients of $\prod_{k=2}^{n+1}(1-x^{a_{k}})$"?
– user
Commented May 4, 2018 at 21:41
• I have a hunch Zeckendorf's theorem could be useful. en.wikipedia.org/wiki/Zeckendorf%27s_theorem Commented May 4, 2018 at 21:59
• @user2661923 When it is true for n=N, the hypothesis will be "n=N, all coefficients are 0,1, or -1", it is not enough. There is some "structure" for these coefficients 0,1,or -1. The hypothesis will be too weak. Commented May 4, 2018 at 21:59
• @Aryabhata any proof Commented May 5, 2018 at 0:42
• Check fq.math.ca/Scanned/34-4/robbins.pdf Effectiveley in notation used in the paper, we seek $a(n)$ when $\{u_n\}=\{F_{n+1}\}$ Commented May 5, 2018 at 5:19

Yufei Zhao, The coefficients of a truncated Fibonacci power series, Fibonacci Quarterly, $$\mathbf{46/47}\,(2008/2009)$$, no. $$1$$, $$53$$-$$55$$, has the following clever inductive proof, which does indeed use a stronger hypothesis.

Say that a polynomial is timid if each of its coefficients is $$-1,0$$, or $$1$$; we want to show that $$A_n(x)$$ is timid for each $$n\ge 1$$, where

$$A_n(x)=\prod_{k=2}^{n+1}\left(1-x^{F_k}\right)\,.$$

We will use auxiliary polynomials $$B_n(x)$$ and $$C_n(x)$$ for $$n\ge 1$$:

\begin{align*} B_1(x)&=1-x^{F_2}-x^{F_3}=1-x-x^2\\ C_1(x)&=1+x^{F_1}-x^{F_3}=1+x-x^2\\ B_n(x)&=A_{n-1}(x)\left(1-x^{F_{n+1}}-x^{F_{n+2}}\right)\text{ for }n\ge 2\\ C_n(x)&=A_{n-1}(x)\left(1+x^{F_n}-x^{F_{n+2}}\right)\text{ for }n\ge 2\,. \end{align*}

Clearly $$A_1(x)=1-x$$, $$B_1(x)$$, $$C_1(x)$$, $$A_2(x)=1-x-x^2+x^3$$, $$B_2(x)=1-x-x^2+x^4$$, and $$C_2(x)=1-x^2-x^3+x^4$$ are timid. Suppose that $$n\ge 3$$, and $$A_k(x),B_k(x)$$, and $$C_k(x)$$ are timid for $$1\le k; we want to show that $$A_n(x),B_n(x)$$, and $$C_n(x)$$ are timid.

\begin{align*} A_n(x)&=A_{n-3}(x)\left(1-x^{F_{n-1}}\right)\left(1-x^{F_n}\right)\left(1-x^{F_{n+1}}\right)\\ &=A_{n-3}(x)\left(1-x^{F_{n-1}}-x^{F_n}\color{red}{-x^{F_{n+1}}+x^{F_{n-1}+F_n}}+x^{F_{n-1}+F_{n+1}}+x^{\color{blue}{F_n}+F_{n+1}}-x^{F_{n-1}+F_n+F_{n+1}}\right)\\ &=A_{n-3}(x)\left(1-x^{F_{n-1}}-x^{F_n}+x^{F_{n-1}+F_{n+1}}+x^{\color{blue}{F_{n-2}+F_{n-1}}+F_{n+1}}-x^{F_{n-1}+F_n+F_{n+1}}\right)\\ &=A_{n-3}(x)\left(1-x^{F_{n-1}}-x^{F_n}\right)+x^{F_{n-1}+F_{n+1}}A_{n-3}(x)\left(1+x^{F_{n-2}}-x^{F_n}\right)\\ &=B_{n-2}(x)+x^{F_{n-1}+F_{n+1}}C_{n-2}(x)\,. \end{align*}

Now

$$\deg B_{n-2}(x)=\sum\limits_{k=2}^{n-2}F_k+F_n=(F_n-F_1-1)+F_n=2F_n-2\,,$$

and

\begin{align*} (F_{n-1}+F_{n+1})-(2F_n-2)&=(F_{n-1}-F_n)+(F_{n+1}-F_n)+2\\ &=-F_{n-2}+F_{n-1}+2\\ &=F_{n-3}+2\\ &>0\,, \end{align*}

i.e., $$F_{n-1}+F_{n+1}>\deg B_{n-2}(x)$$, so $$B_{n-2}(x)$$ and $$x^{F_{n-1}+F_{n+1}}C_{n-2}(x)$$ have no powers of $$x$$ in common. Since $$B_{n-2}(x)$$ and $$x^{F_{n-1}+F_{n+1}}C_{n-2}(x)$$ are both timid, this implies that $$A_n(x)$$ is timid as well.

We can use a similar argument to show that $$B_n(x)$$ is timid:

\begin{align*} B_n(x)&=A_{n-2}(x)\left(1-x^{F_n}\right)\left(1-x^{F_{n+1}}-x^{F_{n+2}}\right)\\ &=A_{n-2}(x)\left(1-x^{F_{n+1}}\color{red}{-x^{F_{n+2}}}-x^{F_n}\color{red}{+x^{F_n+F_{n+1}}}+x^{F_n+F_{n+2}}\right)\\ &=A_{n-2}(x)\left(1-x^{F_n}-x^{F_{n+1}}\right)+x^{F_n+F_{n+2}}A_{n-2}(x)\\ &=B_{n-1}(x)+x^{F_n+F_{n+2}}A_{n-2}(x)\,, \end{align*}

where $$\deg B_{n-1}(x)=2F_{n+1}-2, so $$B_{n-1}(x)$$ and $$x^{F_n+F_{n+2}}A_{n-2}(x)$$ have no powers of $$x$$ in common. Since both are timid, so is their sum, $$B_n(x)$$.

Finally,

\begin{align*} C_n(x)&=A_{n-2}(x)\left(1-x^{F_n}\right)\left(1+x^{F_n}-x^{F_{n+2}}\right)\\ &=A_{n-2}(x)\left(1\color{red}{+x^{F_n}}-x^{\color{green}{F_{n+2}}}\color{red}{-x^{F_n}}-x^{2F_n}+x^{\color{brown}{F_n+F_{n+2}}}\right)\\ &=A_{n-2}(x)\left(1-x^{\color{green}{2F_n+F_{n-1}}}-x^{2F_n}+x^{\color{brown}{2F_n+F_{n+1}}}\right)\\ &=A_{n-2}(x)-x^{2F_n}A_{n-2}(x)\left(1+x^{F_{n-1}}-x^{F_{n+1}}\right)\\ &=A_{n-2}(x)-x^{2F_n}C_{n-1}(x)\,, \end{align*}

where $$\deg A_{n-2}(x)=\sum\limits_{k=2}^{n-1}F_k=F_{n+1}-2$$, and

\begin{align*} 2F_n-(F_{n+1}-2)&=F_n+(F_n-F_{n+1})+2\\ &=F_n-F_{n-1}+2\\ &=F_{n-2}+2\\ &>0\,. \end{align*}

Thus, $$\deg A_{n-2}(x)<2F_n$$, $$A_{n-2}(x)$$ and $$x^{2F_n}C_{n-1}(x)$$ are timid and have no powers of $$x$$ in common, so $$C_n(x)$$ is timid. This completes the induction, and we conclude that $$A_n(x)$$ is timid for each $$n\ge 1$$.

\begin{align*} \prod_{n\ge 2}\left(1-x^{F_n}\right)&=(1-x)\left(1-x^2\right)\left(1-x^3\right)\left(1-x^5\right)\left(1-x^8\right)\ldots\\ &=1-x-x^2+x^5+x^7-x^8+x^{11}-x^{12}-x^{13}+x^{14}+\ldots \end{align*}

is expanded as a formal power series $$\sum\limits_{n\ge 0}a_nx^n$$, $$a_n\in\{-1,0,1\}$$ for each $$n\ge 0$$: the coefficient $$a_n$$ of $$x^n$$ depends only on the factors $$1-x^{F_k}$$ with $$F_k\le n$$, so it is equal to the coefficient of $$x^n$$ in $$A_k(x)$$ for all $$k$$ such that $$F_{k+1}\ge n$$.

By the way, the coefficients $$a_n$$ have a nice combinatorial interpretation. Let $$r_E(n)$$ ($$r_O(n)$$, respectively) be the number of partitions of $$n$$ into an even (odd, respectively) number of distinct parts drawn from the set $$\{F_k:k\ge 2\}$$; then $$a_n=r_E(n)-r_O(n)$$, since each partition of $$n$$ into an even number of parts contributes a term $$x^n$$, and each partition into an odd number of parts contributes a term $$-x^n$$. (The coefficient of $$x^n$$ in $$A_m(x)$$ has a similar interpretation with the sizes of the parts limited to the set $$\{F_2,\ldots,F_{m+1}\}$$.)

Federico Ardila, The coefficients of a Fibonacci power series, Fibonacci Quarterly, $$\mathbf{42}\,(2004)$$, no. $$3$$, $$202$$-$$204$$, makes use of this interpretation to prove a recurrence that allows the $$a_n$$ to be computed quickly and easily in blocks of the form $$[F_m\le n.

Two final observations:

• The sequence $$\langle 0,1,2,4,7,8,11,\ldots\rangle$$ of exponents of non-zero terms of the power series $$\sum_{n\ge 0}a_nx^n$$ is OEIS A151661.

• For $$n\ge 1$$ let $$t_n$$ be the number of non-zero terms in $$A_n(x)$$ then $$t_n=2a(n)$$, where $$a(n)$$ is given by OEIS A104767. (This follows from the comment there by Michael Somos.) Thus, $$t_1=2$$, $$t_2=4$$, $$t_3=6$$, and $$t_n=2t_{n-1}-2t_{n-2}+2t_{n-3}$$ for $$n\ge 4$$.