Why does the difference equation $x_nx_{n+2}=w^5x_n-(w^2+w^3)x_{n+1}+x_{n+2}$ generate cyclic sequences?

Question

Let $w$ be a primitive 5th root of unity. Then the difference equation $$x_nx_{n+2}=x_n-(w^2+w^3)x_{n+1}+x_{n+2}$$ generates a cycle of period 5 for general initial values: $$u,v,\frac{u-(w^2+w^3)v}{u-1},\frac{uv-(w^2+w^3)(u+v)}{(u-1)(v-1)},\frac{v-(w^2+w^3)u}{v-1},u,v, ...$$

For equations of the form $$x_nx_{n+2}=w^{a+b}x_n-(w^a+w^b)x_{n+1}+x_{n+2},\text{ for }w^a+w^b\ne 0$$ with the same globally periodic property, I can show that the only possible periods are 5,8,12,18 and 30.

Curiously, the 'same' equation works for all these periods: $$x_nx_{n+2}=w^5x_n-(w^2+w^3)x_{n+1}+x_{n+2},$$ where $w$ is a primitive $p$th root of unity for $p=5,8,12,18,30$. Is this a fluke or is there a way of seeing why this 'family' of equations always generate cycles?

Answer 1

The substitution $z_n=x_n−1$ really helps us, it leads to the equation $$z_nz_{n+2}=az_{n+1}+b,$$ where $a=-\omega^2-\omega^3, b=1-\omega^2-\omega^3.$ We can easily see that if $z_n=u, z_{n+1}=v$ then $$z_{n-1}=\frac{au+b}{v}, z_{n+2}=\frac{av+b}{u},$$ and $$z_{n-2}=\frac{a^2u+bv+ab}{uv}, z_{n+3}=\frac{a^2v+bu+ab}{uv},$$ so if $a^2=b$ then $z_n$ is $5$-periodic, so and $x_n$. It is true because $$a^2=(\omega^2+\omega^3)^2=2+\omega+\omega^4=1+(1+\omega+\omega^4)=1-\omega^2-\omega^3=b.$$

Answer 2

Too long for a comment: This is to show one periodic sequence that satisfies a similar recurrence in a natural way.

The recurrence $x_nx_{n+2}=x_n+tx_{n+1}+x_{n+2}-(1+t)$ is 6-periodic, for every $t \neq 0$ (and non-degenerate initial values).

We start by observing that the sequence $u,v,v/u,1/u,1/v,u/v,u,v,\ldots$ is 6-periodic, and satisfies the recurrence $y_ny_{n+2}=y_{n+1}$. Now, we can check that the recurrence $y_ny_{n+2}=ry_{n+1}$ is also periodic for any non-zero choice of $r$. In this latter recurrence, substitute $y_n=r(x_n-1)$ and $r=1/t$ to get the first recurrence stated above.

The OP's first recurrence also simplifies in form with the substitution $y_n=x_n-1$, but I don't see a similar natural construction for period 5 (or other periods).

Answer 3

Let us prove that for all nonzero $a,b\in \mathbb{C}$ the difference equation $$x_nx_{n+2}=ax_n+bx_{n+1}+x_{n+2}$$ never generates a cycle of length $8$. Let us denote $u=x_0, y=x_1$.

Suppose the contrary. We know that $$x_{n+2}=\frac{ax_n+bx_{n+1}}{x_n-1}, x_{n-1}=\frac{bx_n+x_{n+1}}{x_{n+1}-a},$$ so for every integer $k$ we can represent $x_k$ as rational function in variables $u,v$: $$x_k=\frac{P_{k}(u,v)}{Q_k(u,v)}.$$

If the equality $x_{-4}=x_4$ is true then $P_{-4}(u,v)Q_{4}(u,v)=P_{4}(u,v)Q_{-4}(u,v)$.

Calculations in Wolfram Mathematica gives the next result for the left side

and for the right side

Looking at some coefficients at $u^iv^j$ we get $$[u^0v^1]: 2a^2b-ab^3=-2a^6b+a^5b^3,$$ $$[u^1v^1]: -a^7+a^6b^2=-a^3+3a^2b^2-ab^4,$$ $$[u^3v^2]: b-ab+b^2-ab^2=-a^2b+a^3b-ab^2+a^2b^2.$$

These equations after excluding some terms turn into (we remember that $a,b\not =0$:

$$ (a^4+1)(2a-b^2)=0, \tag{1}$$ $$[u^1v^1]: b^4+(a^5-3a)b^2+a^2-a^6=0, \tag{2}$$ $$[u^3v^2]: (a-1)(b(a+1)+a^2+1)=0. \tag{3}$$

If $a=1$, then from $(1)$ we have that $b^2=2$. In this case we have $$P_{-4}(u,v)Q_{4}(u,v)-P_{4}(u,v)Q_{-4}(u,v)\not =0,$$ as it equals to

So $a\not =1$, and equation $(3)$ gives us $a\not =-1$ and the next relationship $$b=-\frac{a^2+1}{a+1}. \tag{4}$$

Let us consider the equation $(1)$ and suppose that $b^2=2a$. Then from $(2)$ we have that $a^2-a^6=0$. As $a\not =0,\pm 1$ then $a=\pm i$. But in that case $a=\pm i$, so $b=0$ by $(4)$, contradiction with our assumption.

Hence $a^4+1=0$, so for some odd $k$ we have $$a=e^{ik\pi/4}=\frac{\pm 1 \pm i}{\sqrt{2}}. \tag{5}$$

Joining together $b^2=2a$ and equation $(4)$ we have that $a$ is also a root of polynomial $x^4-2x^3-2x^3-2x+1$ but that's not true, so we get final contradiction.

Answer 4

Another simple case periodic difference equation is the next one, with zero coefficient at $x_{n+1}$: $$x_nx_{n+2}=ax_n+x_{n+2}.$$

Simplicity of this case expressed in existence of nice closed form description for sequence members. Of course given sequence could have only cycles with even period $2T$.

If $T=2k+1$ then $$\frac{1}{x_{-2k-2}}-\frac{1}{x_{2k}}=\frac{1}{u}\left (a^{k+1}-\frac{1}{a^k}\right )+\sum_{i=0}^{k} (-a)^i+\frac{\sum_{i=0}^{k-1} (-a)^i)}{a^k}$$

Coefficient at $1/u$ don't vanish if $a=-1$, so existence of cycle with period $T$ is equivalent to the system of equations: $$a^{2k+1}=1, \tag{1}$$ $$1+(-a)^{k+1}+\frac{1+(-a)^k}{a^k}=0. \tag{2}$$

Multiplying second equation by $a^k$ and recalling equation $(1)$ we get $$a^k+(-1)^{k+1}+1+(-1)^ka^k=0,$$ or $$a^k(1+(-1)^k)=(-1)^k-1,$$ which is impossible while $a$ is some root of unity.

If $T=2k$ then $$x_{-2k}=\frac{-u}{-a^k-u(\sum_{i=0}^{k-1} (-a)^i)}=\frac{a^ku}{1-u(\sum_{i=0}^{k-1} (-a)^i)}=x_{2k},$$

so $a$ should be some primitive $T$-th root of unity - the only case when periodicity can be reached.