A question about Chebyshev polynomials $T_n(x)$, $U_n(x)$, recurrence relations, and power of two $2^n$

Question

I'm interested by the Chebyshev polynomials of the first kind $T_n(x)$ and of the second kind $U_n(x)$, especially $T_n(17)$ and $U_n(17)$.

The recurrence relation of $T_n(17)$ can be written as $a_{n} = 34a_{n-1} - a_{n-2}$ with $a_{0} = 1$ and $a_{1} = 17$.

The recurrence relation of $U_n(17)$ can be written as $a_{n} = 34a_{n-1} - a_{n-2}$ with $a_{-1} = 0$ and $a_{0} = 1$.

During my research, I saw you can write $T_n(17) = T_{2n}(3)$

I found too than $T_{2^n}(3)$ can be written as $a_{n} = 2a_{n-1}^2 - 1$ with $a_{0} = 3$

I found a lot of properties for $T_{2^n}(x)$ but I found no properties for $U_{2^n}(x)$ and no reccurence relations with $a_{n} = ra_{n-1}^p + ma_{n-2}^b + ka_{n-3}^c + ... $

(The value are $1155, 1332869, 1775000307465, 3147895910861898495432209, ...$)

I found than $U_{2^{n+1}}(17) = U_{2^n}(17)^2 - U_{2^n-1}(17)^2$ but it doesn't really help me.

I noticed too for $U_{2^{2n-1}}$ :

$1155 = 3 \cdot 5 \cdot 7 \cdot 11 $

$1775000307465 = 1155 \cdot 3 \cdot 73 \cdot 179 \cdot 197 \cdot 199$

$9900661788578951872471293278006648530622751132705 = 1155 \cdot 23 \cdot 43 \cdot 89 \cdot 131 \cdot 353 \cdot 1187 \cdot 5741 \cdot 11483 \cdot 16633 \cdot 74051 \cdot 37667521 \cdot 52734529$

and probably $U_{2^{2n-1}} = 1155 \cdot K$

I have tried to use properties from Wikipedia and others websites and properties (Fibonacci, Lucas sequences, known closed-formula ...) but, same here, I found no reccurence relation

My question is : it is possible to have a reccurence relation for $U_{2^n}(x)$ of the form $a_{n} = ra_{n-1}^p + ma_{n-2}^b + ka_{n-3}^c + ... $ and especially $U_{2^n}(17)$ ?

EDIT : the closed formula of $U_{2^n}(17)$ is :

$1/48 \cdot ((24 - 17 \sqrt2)(17 - 12 \sqrt2)^{2^n} + (17 + 12 \sqrt2)^{2^n} (24 + 17 \sqrt2))$

And also on Wikipedia, there is the relation $U_{2n}(\sqrt{(x+1)/2}) = W_n(x)$ where $W_n(x)$ is the Chebyshev polynomials of the 4th kind.

Answer 1

While I can't prove the main claim, I can give a proof of the conjecture that $U_{2^{2n-1}}(17)$ is a multiple of $U_{2}(17)=1155$. Moreover, I claim that $U_{2^{2n-1}}(x/2)$ is divisible by $U_2(x/2)$ so long as $x$ is an integer.

There may be a way to do this by recurrence relations alone, but I prefer to make use of matrices. In addition, I will rewrite the Chebyshev polynomials as $S_n(x):=U_n(x/2)$ to avoid excess powers of 2. Then the recurrence relation for the Chebyshev polynomials may be expressed as $$S_{n+1}(x)=xS_n(x)-S_{n-1}(x)$$ with $S_0(x)=1, \,S_{-1}(x)=0$. (One typically starts at $n=0$, but the matrix approach is cleaner with $n=-1$.) For later reference, note that this recurrence ensures that all resulting polynomials have integer coefficients.

This recurrence can be recast as $$\begin{pmatrix} S_{n+1}(x)\\ S_n(x)\end{pmatrix} = \begin{pmatrix} x & -1\\ 1 & 0 \end{pmatrix}\begin{pmatrix}S_{n}(x)\\S_{n-1}(x)\end{pmatrix}.$$ By iterating this, we obtain $$\begin{pmatrix}S_{n}(x)\\ S_{n-1}(x)\end{pmatrix}=\begin{pmatrix} x & -1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} 1\\ 0 \end{pmatrix}.$$ This amounts to $S_n(x)$ being the upper-left matrix element of $M(x)^n$ where $$M(x):=\begin{pmatrix} x & -1 \\ 1 & 0 \end{pmatrix}.$$ From here on I will suppress the $x$-dependence for convenience.

A direct computation now shows that $$M^2=\begin{pmatrix} x^2-1 & -x \\ x & -1 \end{pmatrix}$$ and thus $S_2(x)=x^2-1$. Similarly, one has $$M^3 = \begin{pmatrix} x^3 -2x & 1-x^2 \\ -1+x^2 & -x \end{pmatrix}$$ If we consider this matrix power modulo $x^2-1$, then $$M^3 \equiv \begin{pmatrix} -x & 0 \\ 0 & -x \end{pmatrix}$$ and moreover $$M^6 = \begin{pmatrix} x^2 & 0 \\ 0 & x^2 \end{pmatrix}\equiv \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$$ Thus $M^6$ acts as the identity when taken modulo $x^2-1$. But $$M^{2^{2(n+1)-1}}=[M^6]^{2^{2(n-1)}} M^{2^{2n-1}}\equiv M^{2^{2n-1}}\mod x^2-1.$$ Iterating, we conclude that $$M^{2^{2n-1}}\equiv M^2\equiv \begin{pmatrix} 0 & -x \\ x & -1 \end{pmatrix}.$$ But this means $S_{2^{2n-1}}(x)\equiv 0$ modulo $x^2-1$, i.e., $S_{2^{2n-1}}(x)$ is divisible by $S_2(x)=x^2-1$.

Since $S_{2^{2n-1}}(x)$ and $x^2-1$ are integer polynomials, the above remains valid if we replace $x$ with any integer. In particular, when $x=34$ we conclude that $S_{2^{2n-1}}(34)=U_{2^{2n-1}}(17)$ is divisible by $S_2(34)=U_2(17)=34^2-1=1155$.