# Some identities for polynomials defined by their generating function.

This question is part of Question 456683 in MO which has not been answered.

Define polynomials $$(u_n(x))=(1,0,-x^2,x^2 -1,x^4-x^2,-2x^4+3x^2, -x^6+3x^4-3x^2+1,\dots)$$ by their generating function $$\sum_{n \geq 0}u_n(x)z^n=\frac{1+z}{1+z+x^2 z^2+z^3+z^4}.$$ Then $$u_n(x)=\sum_{0\leq 2j\leq n}(-1)^{n-j}a_{j,n-2j}x^{2j}$$ with $$\sum_{n \geq 0}a_{j,n}z^n=\frac{1}{(1-z)^j (1-z^3)^{j+1}}$$ because $$\sum_{n,j}(-1)^{n-j} a_{j,n-2j}x^{2j}z^n=\sum_j(-1)^j (x z)^{2j}\sum_n(-1)^n a_{j,n-2j}z^{n-2j} =\sum_j \frac{(x z)^{2j}}{(1+z)^j (1+z^3) ^{j+1}}=\frac{1+z}{1+z+x^2 z^2 +z^3+z^4}.$$

Computations suggest that

$$u_n(x) u_{n+6}(x)- u_{n+3}(x)^2=x^2 (u_{n+1}(x) u_{n+5}(x)- u_{n+3}(x)^2).$$

More generally let $$r,s$$ be positive integers and $$h_n(x)=u_n(x)u_{n+r+s}(x)-u_{n+r}(x)u_{n+s}(x)$$. Then $$h_n(x)$$ satisfies the recursion $$h_{n+5}(x)-h_n(x)=(x^2-1)(h_{n+4}(x)+ h_{n+3}(x)- h_{n+2}(x)- h_{n+1}(x)).$$

Is there a simple method to prove these conjectures?

• Does this recurrence hold for $h_n(x) = u_n(x) u_{n+r}(x)$? Nov 26, 2023 at 16:47
• Judging from my own answer, no, $u_n(x) u_{n+r}(x)$ should be a recurrence of order $9$ rather than $5$. Nov 26, 2023 at 18:58

Here's the proof that $$h_n(x) = (x^2-1)(h_{n-1}(x)+h_{n-2}(x)-h_{n-3}(x)-h_{n-4}(x))+h_{n-5}(x)$$ for $$h_n(x) = u_n(x) u_{n+r+s}(x) - u_{n+r}(x) u_{n+s}(x)$$, as defined above:

Generally, the way it is defined, it holds that $$-u_n(x) = u_{n-1}(x)+x^2 u_{n-2}(x) + u_{n-3}(x) + u_{n-4}(x).$$ In other words, $$u_n(x)$$ is a linear recurrence with a characteristic polynomial $$p(z) = z^4+z^3+x^2z^2+z+1.$$ What it means is, assume $$p(z) = (z-z_1)(z-z_2)(z-z_3)(z-z_4),$$ then, assuming that the roots are distinct, $$u_n(x)$$ can be represented as $$u_n(x) = a_1(x) z_1(x)^n + \dots + a_4(x)z_4(x)^n.$$

Using this result, we can express $$h_n(x)$$ defined above as $$h_n(x) = \sum\limits_{i=1}^4 \sum\limits_{j=1}^4 a_i a_j\left(z_i^n z_j^{n+r+s}-z_i^{n+r} z_j^{n+s}\right).$$

To understand why the expression above results into a linear recurrence of small degree, we should note that for $$x \in (\sqrt{6}, +\infty)$$, if $$r$$ is one of the roots, then the full set of roots is $$\{r,r^*,\frac{1}{r},\frac{1}{r^*}\}$$, where $$r^*$$ is complex conjugate of $$r$$. This stems from the following facts:

1. For $$x > 0$$, there are no real roots of $$p(z)$$;
2. $$p(z) = p(z)^*$$, meaning that for any root $$r$$, its conjugate $$r^*$$ must also be a root;
3. $$p(z) = z^4 p(\frac{1}{z})$$, meaning that for any root $$r$$, its inverse $$\frac{1}{r}$$ must also be a root.
4. Generally, $$x^2 = z_1 z_2 + z_1 z_3 + z_1 z_4 + z_2 z_3 + z_2 z_4 + z_3 z_4$$, meaning that for $$x > \sqrt{6}$$ one of the roots must be not on the unit circle, hence having distinct conjugate and inverse.

Playing with Wolfram a bit, we can also notice that the actual transition point from roots on unit circle to the set of $$4$$ roots as described above is even earlier, at $$x > \frac{3}{2}$$ rather than $$x > \sqrt{6}$$. This is probably due to the fact that at $$x=\frac{3}{2}$$ we have $$p(z) = (z^2+\frac{z}{2}+1)^2$$, hence the bifurcation.

Knowing that the roots are $$\{r, r^*, \frac{1}{r}, \frac{1}{r^*}\}$$, we may notice that all cases of $$z_i = z_j$$ will cancel each other out, thus only the following possible products $$z_i z_j$$ will survive: $$z_i z_j \in \left\{1,\|r\|,\frac{r^2}{\|r\|}, \frac{(r^*)^2}{\|r\|},\frac{1}{\|r\|}\right\}.$$ So, while the initial recurrence corresponded to $$4$$ distinct roots, the new one will correspond to $$5$$ distinct roots. Since you provided the resulting recurrence in your answer, my guess would be that if the initial characteristic polynomial is $$p(z) = (z-r)(z-r^*)\left(z-\frac{1}{r}\right)\left(z-\frac{1}{r^*}\right) = x^4+x^3+x^2z^2+z+1,$$ then the final one is $$q(z) = (z-1)(z-\|r\|)\left(z-\frac{r^2}{\|r\|}\right)\left(z-\frac{(r^*)^2}{\|r\|}\right)\left(z-\frac{1}{\|r\|}\right),$$ and from your resulting formula it seems that, in fact, $$q(z) = z^5 - (x^2-1)(z^4+z^3-z^2-z) - 1.$$

Well, so far we only somewhat proved this result for $$x \in (\sqrt{6},+\infty)$$, but with generating functions it's quite typical that the results that are true for some continuous range of $$x$$ are also true for $$x$$ as a formal variable, so I hope this should do it.

UPD. This can also be shown symbolically with sympy:

from sympy import *

x, z = symbols('x z')

p = z**4 + z**3 + x**2 * z**2 + z + 1
r = list(roots(p, z))

q = (prod(z-r[i]*r[j] for i in range(4) for j in range(i))).expand()
expand(factor(q) / gcd(q, q.diff(z))) # remove multiple roots


Yields $$q(z) = - x^{2} z^{4} - x^{2} z^{3} + x^{2} z^{2} + x^{2} z + z^{5} + z^{4} + z^{3} - z^{2} - z - 1$$, which is, indeed $$q(z) = z^5 - (x^2-1)(z^4+z^3-z^2-z) - 1,$$ thus proving that the recurrence for $$h_n(x)$$ is, indeed $$h_n(x) = (x^2-1)(h_{n-1}(x)+h_{n-2}(x)-h_{n-3}(x)-h_{n-4}(x))+h_{n-5}(x).$$

• @ Oleksandr Kulkov: This explains why these expressions have a simpler recurrence. Nov 27, 2023 at 13:38
• Also note the update for more conclusive proof that $q(z)$ is exactly as I assumed. Nov 27, 2023 at 13:57

The question is about a sequence of polynomials in $$\,x\,$$ whose generating function is

$$\sum_{n \geq 0}u_nz^n := \sum_{n \geq 0}u_n(x)z^n = \frac{1+z}{1+z+x^2 z^2+z^3+z^4}. \tag1$$

This immediately implies that the sequence satisfies a linear recurrence with coefficients that are polynomials in $$\,x.\,$$ It is easy to verify using only the linear recurrence the following results for all integer $$\,n\,$$ where $$\,y := x^2-1\,$$

\begin{align*} u_{n+4} &= -u_n - u_{n+1} - x^2u_{n+2} - u_{n+3}, \\ u_{n+5} &= u_n +y\,u_{n+2} -y\,u_{n+3}, \\ u_{n+6} &= y\,u_n + x^2u_{n+1} +x^2y\,u_{n+2} + 2y\,u_{n+3}, \\ u_{n+7} &= -2y\,u_n -y\,u_{n+1} +x^2(3-2x^2)u_{n+2} +y(y-1)u_{n+3}. \tag2 \end{align*}

Define the sequence of polynomials

$$g_n := (u_n u_{n+6} -u_{n+3} ^2) - x^2(u_{n+1} u_{n+5} - u_{n+3} ^2). \tag3$$

Use the results in equation $$(2)$$ to verify that

$$g_{n+1} = g_n = (u_n+u_{n+3})^2 + x^2(u_{n+1}u_{n+3} - u_{n+1}u_{n+2} + u_nu_{n+2}). \tag4$$

Use induction to conclude that $$\,g_n = g_0 := y\,I_1\,$$ for all integer $$\,n.\,$$

From equation $$(1)$$ the first few values of the $$\,u\,$$ sequence are

$$u_{-1} = 0,\;\; u_0 = 1,\;\; u_1 = 0,\;\; u_2 = -x^2,\;\; u_3 = x^2-1. \tag5$$

Verify that $$\,g_0 = I_1 = 0\,$$ for these initial values of $$\,u.\,$$

This proves the first conjecture

$$u_n(x)u_{n+6}(x)-u_{n+3}(x)^2 = x^2(u_{n+1}(x)u_{n+5}(x) - u_{n+3}(x)^2). \tag6$$

Define the sequence

$$f_n := (u_{n+1} + u_{n+2})^2 + y\,u_{n+1}u_{n+2} + u_nu_{n+1} +(u_{n+2}-u_n)u_{n+3}. \tag7$$

Similar to equation $$(4)$$ verify that $$\,f_{n+1} = f_n\,$$ and conclude that $$\,f_n = f_0 := I_2\,$$ for all integer $$\,n.\,$$ Verify that $$\,f_0=I_2=1\,$$ For the initial values of $$\,u\,$$ in equation $$(5)$$.

Verify the general recurrence result

\begin{align*} I_1u_{n+4}u_{n-4}=\; & (2I_1+x^2I_2)u_{n+3}u_{n-3} + ((y^2-2)I_1 - x^4I_2)u_{n+2}u_{n-2} +\\ & (1-y)I_1u_{n+1}u_{n-1} + y((1-y)I_1 + x^2I_2)u_nu_n. \tag8 \end{align*}

Verify that equation $$(8)$$ is equivalent to equation $$(6)$$ if $$\,I_1=0\,$$ and $$\,I_2=1\,$$ which is implied by equation $$(5)$$.

Note that so far, all the algebra required can easily be done by hand.

Given any two integers $$\,r,s\,$$ define the sequence

$$h_n := u_n u_{n+r+s} -u_{n+r} u_{n+s} . \tag9$$

It is conjectured that the sequence $$\,h_n\,$$ satisfies the recursion

$$h_{n+5}-h_n = y(h_{n+4} + h_{n+3} - h_{n+2} - h_{n+1}). \tag{10}$$

This is surprisingly simple to prove in great generality. Suppose that for a fixed positive integer $$\,m\,$$ and constants $$\,c_k\,$$ the sequence $$\,u\,$$ satisfies the linear recursion

$$u_n := \sum_{k=1}^m c_k u_{n-k}. \tag{11}$$

In the general case, where the characteristic polynomial of the recursion has no repeated roots, there exists constants $$\,a_k\,$$ and roots $$\,r_k\,$$ such that

$$u_n = \sum_{k=1}^m a_k r_k{}^n. \tag{12}$$

That is, the sequence $$\,u\,$$ is a linear combination of powers of the roots $$\,r.\,$$ Suppose $$\,v\,$$ and $$\,w\,$$ are any two sequences with the same roots. Then their product sequence is a linear combination of powers of the product of two roots. That is, there exists constants $$\,b_{i,j}\,$$ which only depend on the roots $$\,r_k\,$$ such that

$$h_n:=v_n w_n = \sum_{1\le i\le j\le m} b_{i,j}(r_ir_j)^n. \tag{13}$$

This implies that there exists constants $$\,d_k\,$$ which depend on the roots $$\,r_k\,$$such that there is a linear recursion for $$\,h\,$$

$$h_n = \sum_{k=1}^M d_k h_{n-k}. \tag{14}$$

where $$\,M\le m(m+1)/2.\,$$ Note that this same recursion holds for any linear combination of products of two sequences with the same recursion in equation $$(11)$$. Thus, in particular, the recursion in equation $$(14)$$ holds for the sequence in equation $$(9)$$.

For the particular sequence $$\,u_n\,$$ defined in equation $$(1)$$ it suffices to show that $$\,h_n := u_n^2\,$$ satisfies the recursion in equation $$(10)$$ using the same techniques used to prove the first conjecture and this implies that the sequence $$\,h\,$$ in equation $$(9)$$ also satisfies the same recursion. Note that the characteristic polynomial for $$\,u\,$$ is palindromic which leads to the simple form of the recursion in equation $$(10)$$.

This proves the second conjecture.

I used Wolfram Mathematica extensively to study the natural generalization of the original sequence of polynomials $$\,u_n.\,$$ Here is a summary of the results I found.

Define the sequence $$\,u_n\,$$ by the recursion with constants $$\,c_2,c_3$$

$$u_n = -(c_2 u_{n-1} + c_3 u_{n-2} + c_2 u_{n-3} + u_{n-4}). \tag{15}$$

Define the sequence $$\,h_n\,$$ as in equation $$(9)$$. Then it satisfies the recursion

$$h_{n+5} - h_n = (1-c_3)(h_{n+4} - h_{n+1}) + (c_2^2-c_3)(h_{n+3} - h_{n+2}) \tag{16}$$

which is the generalization of equation $$(10)$$

Notice the general Somos-8 sequence identity

$$v_0 u_{n+4}u_{n-4} = -(v_1 u_{n+3}u_{n-3} + v_2 u_{n+2}u_{n-2} + v_3 u_{n+1}u_{n-1} + v_4 u_{n}u_{n}) \tag{17}$$

where the constants $$\,v_0,v_1,v_2,v_3,v_4\,$$ depend on $$\,c_2,c_3\,$$ and the initial values $$\,u_0,u_1,u_2,u_3.\,$$ This is the generalization of equation $$(6)$$.

• @ Somos: Very nice! You first express $u_{n+4},\dots, u_{n+7}$ as linear expressions in $u_n, \dots, u_{n+3}.$ It suffices to verify this for small $n.$ Substituting this in $g_n(x)$ and $g_{n+1}(x)$ gives the same formula $F(u_n,u_{n+1},u_{n+2},u_{n+3})$ which by induction gives $g_n(x)=0.$ Nov 27, 2023 at 13:27
• @JohannCigler Thanks, but almost correct. Expressing $\,u_{n+4},\dots,u_{n+7}\,$ as a linear combination in $\,u_n,\dots,u_{n+3}\,$ does not need verification for small $\,n\,$, but comes directly from the recursion $\,u_{n+4} = -u_n - u_{n+1} - x^2u_{n+2} - u_{n+3},\,$ which comes from equation $(1)$. I am still working on the 2nd conjecture. Nov 27, 2023 at 15:01
• Note that the order of the recurrence in $(10)$ is smaller than the one in $(14)$, and they're, generally, different recursions. E.g. $h_n = u_n u_{n+r}$ might not adhere to the one in $(10)$, but it will always adhere to the one in $(14)$. Nov 29, 2023 at 18:00
• @OleksandrKulkov Good point! I forgot that little detail. I will add more explanation. Nov 29, 2023 at 18:02