Fibonacci polynomials and factorization redux

Question

I recently asked a question about factorizing a certain expression involving Fibonacci and Lucas polynomials. That question had a very simple and nice answer, but now I've come across another similar question which has me stumped.

Conjecture: The polynomial $4- F_n(x)^4(x^2+3)$ factors as $H_n(x)H_n(-x)$ for some integer polynomial $H_n(x)$, where $F_n(x)$ is the nth Fibonacci polynomial.

Any ideas?

(In case anybody is wondering why I care about these question, they are related to calculating the Conway polynomial of certain families of knots.)

Edit: As requested, here are the first few examples. Let $G_n(x)=4- F_n(x)^4(x^2+3)$. Then

• $G_1(x)=(1+x)(1-x)$
• $G_2(x)=(1+x)(1-x)(2+x^2)^2$
• $G_3(x)=(-1 - 3 x + 2 x^2 - 4 x^3 + x^4 - x^5) (-1 + 3 x + 2 x^2 + 4 x^3 + x^4 + x^5)$
• $G_4(x)= (2 - 4 x + 4 x^2 - 10 x^3 + 4 x^4 - 6 x^5 + x^6 - x^7) (2 + 4 x + 4 x^2 + 10 x^3 + 4 x^4 + 6 x^5 + x^6 + x^7)$
• $G_5(x)=(-1 - 5 x + 6 x^2 - 20 x^3 + 11 x^4 - 21 x^5 + 6 x^6 - 8 x^7 + x^8 - x^9) (-1 + 5 x + 6 x^2 + 20 x^3 + 11 x^4 + 21 x^5 + 6 x^6 + 8 x^7 + x^8 + x^9)$

Edit 2: Following Will Jagy's ideas, define a family of polynomials $H_n(x)$ by $H_0(x)=2$, $H_1(x)=-1+x$ and then $$H_{n+2}(x)=(x^2+2)H_{n+1}(x)-H_n(x)+(-1)^n(6+2x^2)$$ for $n\geq 0$. Computations show that $$H_n(x)H_n(-x)=G_n(x)$$ for $n\leq 20$. What remains is to prove that this is a valid formula in general.

Answer 1

This looks a little better, $H_1(x) = 1 + x, \; H_2(x) = 2 + 2x + x^2 + x^3, \; H_3(x) = -1 + 3 x + 2 x^2 + 4 x^3 + x^4 + x^5, $ then $$ H_{n+2}(x) = (2+ x^2) H_{n+1}(x) - H_n(x) + OTHERERROR_{n+2}(x), $$ where this way the error stays quadratic, by hand calculations the first three error terms come out $$ -4 + x^2, \; 6 + 2 x^2, \; -6 - 2 x^2... $$

Answer 2

Edit: I think all this recurrence relation stuff is a red herring. Instead, it seems to be more relevant that the polynomials $F_n(x)$ form a basis for $\mathbb Z[x]$, and that one can multiply them according to the formula: $$F_n(x)F_m(x)=F_{n+m-1}(x)-F_{n+m-3}(x)+\cdots\pm F_{|n-m|+1}(x)$$ where the signs alternate. This can be proven by considering the formula $F_n=\frac{\alpha^n-\bar{\alpha}^n}{\alpha-\bar{\alpha}}$. After playing around, I came up with the following pretty simple looking conjecture, which can be easily verified by computer for low values of $n$. This would completely solve the original problem.

Conjecture: For all $n\geq 1$, $$4-(F_3(x)+2F_1(x))F_n(x)^4=\left(F_1(x)+F_3(x)-F_5(x)+\cdots+(-1)^nF_{2n-1}(x)\right)^2-F_{2n}(x)^2.$$ The signs of $F_1$ and $F_3$ are both positive, but they alternate after that.

Original answer: I wanted to record here the derivation of a closed formula for the recursively defined $H_n(x)$ which ultimately expresses it in terms of Fibonacci polynomials.

Letting $H_0=2, H_1=-1+x$ and $H_n=(x^2+2)H_{n-1}-H_{n-2}+(-1)^n(6+2x^2$, form the generating function $\varphi(x,y)=\displaystyle \sum_{n=0}^\infty H_n(x)y^n$. Then \begin{align*} (x^2+2)y\varphi(x,y)&=\sum_{n=1}^\infty (x^2+2)H_{n-1}y^n\\ -y^2\varphi(x,y)&=\sum_{n=2}^\infty -H_{n-2}y^n\\ \frac{y^2(6+2x)}{1+y}&=\sum_{n=2}^\infty (-1)^n(6+2x^2)y^n \end{align*} Adding these all up, we get $$(x^2+2)y\varphi(x,y)-y^2\varphi(x,y)+\frac{y^2(6+2x)}{1+y}=\sum_{n=2}^\infty H_ny^n+(x^2+2)(2y)$$ Now use that $\sum_{n=2}^\infty H_ny^n=\varphi(x,y)-(-1+x)y-2$ and solve for $\varphi(x,y)$ to get the generating function: $$\varphi(x,y)=\frac{1}{y^2-(x^2+2)y+1}\left(2+(-2x^2+x-5)y+\frac{y^2(6+2x)}{1+y}\right)$$ The roots of $y^2-(x^2+2)y+1$ as a polynomial in $y$ are $\zeta=\frac{x^2+2+x\sqrt{x^2+4}}{2}$ and $\overline{\zeta}=\frac{x^2+2-x\sqrt{x^2+4}}{2}$. Notice $\zeta\overline{\zeta}=1$. Using partial fractions, one sees that \begin{align*} \frac{1}{y^2-(x^2+2)y+1}&=\frac{1}{\zeta-\overline{\zeta}}\left(\frac{1}{y-\zeta}-\frac{1}{y-\overline{\zeta}}\right)\\ &=\frac{1}{\zeta-\overline{\zeta}}\left(\frac{-\overline{\zeta}}{1-y\overline{\zeta}}+\frac{\zeta}{1-y\zeta}\right)\\ &=\frac{1}{\zeta-\overline{\zeta}}\left(-\overline{\zeta}\sum_{n=0}^\infty \overline{\zeta}^ny^n+\zeta \sum_{n=0}^\infty \zeta^ny^n\right)\\ &=\sum_{n=0}^\infty \left(\frac{\zeta^{n+1}-\overline{\zeta}^{n+1}}{\zeta-\overline{\zeta}} \right)y^n \end{align*} Let $q_n=\left(\frac{\zeta^{n+1}-\overline{\zeta}^{n+1}}{\zeta-\overline{\zeta}} \right)$. Then $\displaystyle \frac{1}{y^2-(x^2+2)y+1}=\sum_{n=0}^\infty q_n y^n$. Plugging in to the earlier formula, and skipping some algebra, we get that $H_0=2$, $H_1=2q_1+(-2x^2+x-5)q_0=-1+x$ and $$ H_n=(6+2x^2)\sum_{k=0}^{n-2}(-1)^{n-k}q_k+2q_n+(-2x^2+x-5)q_{n-1} $$ for $n\geq 2$.

Now recall that the Fibonacci polynomial $$F_n=\frac{\alpha^n-\overline{\alpha}^n}{\alpha-\overline{\alpha}}$$ where $\alpha=\frac{x+\sqrt{x^2+4}}{2}$. Note that $\overline{\alpha}+\alpha=x$ and that $\alpha^2=\zeta$. Then $$q_n=\frac{\zeta^{n+1}-\overline{\zeta}^{n+1}}{\zeta-\overline{\zeta}}=\frac{\alpha^{2n}-\overline{\alpha}^{2n}}{\alpha^2-\overline{\alpha}^2}=\frac{1}{\alpha+\overline{\alpha}}\frac{\alpha^{2n}-\overline{\alpha}^{2n}} {\alpha-\overline{\alpha}}=x^{-1}F_{2n+2}.$$

So we get $$H_n(x)=(6+2x^2)\left(\sum_{k=0}^{n-2}(-1)^{n-k}x^{-1}F_{2k+2}\right)+2x^{-1}F_{2n+2}+(-2x^2+x-5)x^{-1}F_{2n}$$ for $n\geq 2$.

It is interesting to notice that in this formula, the only odd degree terms come from the $F_{2n}$ term on the right. So we have \begin{align*}&H_n(x)H_n(-x)=\\&\left[ (6+2x^2)\left(\sum_{k=0}^{n-2}(-1)^{n-k}x^{-1}(F_{2k+2})\right)+2x^{-1}F_{2n+2}+(-2x^2-5)x^{-1}F_{2n}\right]^2-F_{2n}^2\end{align*}

Thus the original question is reduced to the following complicated identity on Fibonacci polynomials: \begin{align*}&4-(x^2+3)F_n(x)^4=\\&\left[ (6+2x^2)\left(\sum_{k=0}^{n-2}(-1)^{n-k}x^{-1}(F_{2k+2})\right)+2x^{-1}F_{2n+2}+(-2x^2-5)x^{-1}F_{2n}\right]^2-F_{2n}^2\end{align*}

Answer 3

$F_n(x)$ satisfies a length 2 homogeneous linear recurrence with coefficients in $k = \mathbb{C}(x)$. Your guess for $H_n(x)$ satisfies a length 3 homogeneous linear recurrence again with coefficients in $k$. Similarly $H_n(-x)$ also satisfies a length 3 recurrence.

Standard results about such so called $C$-finite sequences tells us that $A_n = 4- F_n(x)^4(x^2+3) - H_n(x)H_n(-x)$ satisfies a homogeneous linear recurrence of length at most 15. In particular if $A_n = 0$ for the first 15 values of $n$ it must be true for all values of $n$.

So since you checked this up to $n=20$ you are already done.