Show that these non-linear recursions produce integers only

Question

The recurrence is of third order:

Start with \begin{align*}a_0(x)&=1\\ a_1(x)&=1\\ a_2(x)&=x \end{align*} and then \begin{align*}a_{n+3}(x)&=\frac{a_{n+2}^2(x)-a_{n+1}^2(x)}{a_{n}(x)}.\end{align*}

The calculation and factorization of $a_n(x)$ for $3\le n \le 6$ gives the following results: \begin{align*} a_3(x)&= (x+1)(x-1)\\ a_4(x)&=(x^2 + x -1)(x^2-x-1)\\ a_5(x)&=x(x^2 -2)(x^4-4x^2+2)\\ a_6(x)&=(x^6 +x^5-5x^4-4x^3+6x^2+3x-1)(x^6 -x^5-5x^4+4x^3+6x^2-3x-1)\\ \end{align*}

Questions:

• Any reference for this ?
• Show that $a_n(x)$ is an integer coefficient polynomial. It would be of degree $F_{n+1} -1$, where $F_n$ is a Fibonacci number.
• Is it true that $a_n(x)$ divides $a_{2n+1}(x)$?
• For $k \in \mathbb N, k>1$, is there a general close form for $a_n(k)$?

For $k=2$, we obviously have $a_n(2)=F_{n+1}$.

For $k=3$, we have $a_n(3)=F_{2F_{n+1}}$.

What about $a_n(4)$?

Answer 1

Nice recursion!! However, let us change the name and indexing of your sequence. Notice that if $\,U_n(x)$ is the Chebyshev polynomial of the second kind, then $\, U_n(x/2)$ is a polynomial in $x$ with integer coefficients. Define $\, P_n(x) := U_{F_n - 1}(x/2).\,$ Your sequence $\, a_n(x) = P_{n+1}(x).\,$ Please note the different indexing.

Check the following equations hold true for all integer $\,n$ $$ P_1(x) = P_2(x) = 1, \,\, P_3(x) = x,\,\, P_n(x)P_{n+3}(x) = P_{n+2}^2(x) - P_{n+1}^2(x).$$

Both $\,U_{n-1}(\cos\theta) = \sin(n\theta)/\sin(\theta)\,$ and $\,F_n = U_{n-1}(i/2)/i^{n-1}\,$ are divisibility sequences, hence $\,P_n(x)\,$ divides $\,P_{kn}(x)\,$ for all integer $\,n,k\,$ where $\,P_n(x)\ne 0.\,$ We also have $\,P_n(x) = -(-1)^n P_{-n}(x)\,$ for all integer $\,n.\,$

Answer 2

Here is another proof that $a_n$ is integer, which is somewhat more elementary as it does not require the knowledge of Chebyshev Polynomials. It follows the same lines of reasoning as in Malouf, J.L., An integer sequence from a rational recursion, Discrete Mathematics 110 (1992) 257-261.

We suppose (induction hypothesis) that all the $a_j$ are integers up to $j=n$ with $n\ge5$.

We let $B_6=a_{n+1}$, $B_5=a_n$, $B_4=a_{n-1}$,, $B_3=a_{n-2}$, $B_2=a_{n-3}$, $B_1=a_{n-4}$ and $B_0=a_{n-5}$.

It is easy to verify that $a_0, a_1, a_2, a_3, a_4$ and $a_5$ are integers, then it suffices to show that $B_6$ is integer. This amounts at showing that $$\tag0 B_5^2-B_4^2\equiv 0 \pmod {B_3}.$$ If there exists a prime $p$ such that $p$ divides two consecutives members $a_j$ and $a_{j-1}$ of the sequence (up to the index $n$, all the members are integers by hypothesis), then since $a_{j-2}^2= a_{j-1}^2-a_ja_{j-3}$, then $p$ divides $a_{j-2}$, which by repetition leads to $p$ divides $a_1=1$, which is impossible, so we have shown that two consecutive members of the sequence are coprime, as long as they are integers.

We also show that $B_1$ is coprime to $B_3$ for suppose $p$ divides $B_3$, then $p$ does not divide $B_1$, otherwise since $B_1B_4 =B_3^2-B_2^2$, we would have $p$ divides $B_2$, which is impossible.

We have \begin{align*} \tag1 B_0B_3 &=B_2^2-B_1^2 \equiv 0 \pmod {B_3}\\ \tag2 B_1B_4 &=B_3^2-B_2^2\equiv -B_2^2\pmod {B_3}\\ \tag3 B_2B_5 &=B_4^2-B_3^2 \equiv B_4^2\pmod {B_3} \end{align*} From $(2)$ and $(1)$, we obtain $B_1B_4 \equiv -B_1^2\pmod {B_3}$, but since $B_1$ and $B_3$ are coprime that is $$\tag4 B_4 \equiv -B_1\pmod {B_3}.$$ From $(3)$, $(4)$ and $(1)$, we obtain $B_2B_5 \equiv B_2^2\pmod {B_3}$, but since $B_2$ and $B_3$ are coprime that is $$\tag5 B_5 \equiv B_2\pmod {B_3}.$$

Finally $(0)$ follows from $(4)$,$(5)$ and $(1)$. $\ \ \ \ \ \ \square$