a periodic sequence

Let $w$ be a primitive $2m$th root of unity. Then the sequence generated by $$x_{n+2}=\frac{w^4x_n-(w^3+w^2)x_{n+1}-wx_nx_{n+1}}{-w-(w^3+1)x_n+w^2x_{n+1}}$$ appears to have period $2m$ for almost all initial terms.

I can prove this for (very) small $m$ and check it numerically for other values of $m$. I should be grateful for any ideas regarding a general proof.

• In the formula, $w$ is the root as stated. – S. Dolan Mar 9 '18 at 8:05
• In the formula, $w$ is the root as stated. If you multiply the expression out you obtain an equality between a linear function of the $x_i$ and a homogeneous quadratic function. I was investigating the nature of sequences generated by such expressions when I discovered this property. – S. Dolan Mar 9 '18 at 8:14

The equation can be written as an equality of a homogeneous quadratic and a linear polynomial: $$wx_nx_{n+1}-(w^3+1)x_nx_{n+2}+w^2x_{n+1}x_{n+2}=w^4x_n-(w^3+w^2)x_{n+1}+wx_{n+2}.$$ Sequences with $x_{n+1}-wx_n=0$ send both the quadratic part and linear part to zero. This suggests writing the equation in the form $$w^2(x_{n+2}+w)(x_{n+1}-wx_n)=(x_n+w)(x_{n+2}-wx_{n+1}).$$ Restricting to sequences not of the form $x_i=Aw^i,$ this is equivalent to $$w^2\frac{(x_{n+2}+w)(x_{n+1}+w)}{x_{n+2}-wx_{n+1}}=\frac{(x_n+w)(x_{n+1}+w)}{x_{n+1}-wx_n}.$$

This shows that the numbers $$y_n=\frac{(x_n+w)(x_{n+1}+w)}{x_{n+1}-wx_n}$$ satisfy $y_{n+1}=w^{-2}y_n,$ and are therefore $2m$-periodic.

If the $y_n$ are fixed, the map $x_n\mapsto x_{n+1}$ can be considered as a Möbius transformation: $$x_{n+1}=\frac{(wy_n+w)x_n+w^2}{-x_n+(y_n-w)}.$$

and the problem is reduced to showing that the composition $x_0\mapsto x_1\mapsto \cdots\mapsto x_{m}$ is an involution - doing it twice ends up at $x_0.$ This map is represented by the matrix product $A({y_{n-1}})\cdots A(y_0)$ where $$A(y)=y\begin{pmatrix}w&0\\0&1\end{pmatrix}+\begin{pmatrix}w&w^2\\-1&-w\end{pmatrix}.$$

Let $p(y)=\operatorname{tr}(A({yw^{-2(m-1)}})\cdots A(yw^{-2})A(y)).$ Then $p$ is a degree-$m$ polynomial in $y.$ By conjugation invariance of trace we have $p(y)=p(yw^2),$ which means $p$ is of the form $Ay^m+B,$ where $A=w^{-2(m-1)+\dots-2-0}\operatorname{tr}\begin{pmatrix}w^m&0\\0&1\end{pmatrix}=0$ and $B=\operatorname{tr}\begin{pmatrix}w&w^2\\-1&-w\end{pmatrix}^m=0.$ So $p=0,$ which means $x_0\mapsto x_m$ is an involution as required.

This argument shows that most choices of $x_n,x_{n+1}$ give period $2m.$ It is also possible for a sequence to have period $m.$ There will generally be two such sequences for each $y_0,$ corresponding to the fixed points of the Möbius transformation $x_0\mapsto x_m.$

• Many thanks Dap for a superb solution. Sorry for delay in replying - I was away for a few days. I had used your initial suggestion to obtain the same product of pairs of matrices but I then multiplied out. Each term is then a product of $m$ matrices and the traces of all the terms which can be obtained from each other by cyclic interchanges of these products can be added. Effectively the same as your subtle analysis of the polynomial in $y$ but much less elegant. Thanks again. – S. Dolan Mar 14 '18 at 9:01