Substitution in Palindromic Polynomial

Question

Given a palindromic polynomial $p(x)$ of degree $2n$, where the coefficients are $a_{i}=a_{2n-i}$. It is known that there exists a polynomial $q$ with

$$ x^n q(x + 1/x) = p(x) $$

I'm looking for an explicit expression for the coefficients of $q$.

Answer 1

Let $\,u=x+\frac{1}{x}\,$, then:

$$q(u) = \frac{1}{x^n} p(x) = a_n+\sum_{k=0}^{n-1} a_k\left(x^{n-k}+\frac{1}{x^{n-k}}\right) = a_n + \sum_{k=0}^{n-1} a_k \cdot b_{n-k}(u)$$

$b_k(u)=x^k+\frac{1}{x^k}$ is a polynomial of degree $k$ in $u$ recursively defined as $b_0 = 2, b_1 = u$ and:

$$ b_{k+1}=x^{k+1}+\frac{1}{x^{k+1}}=\left(x^k+\frac{1}{x^k}\right)\left(x+\frac{1}{x}\right)-\left(x^{k-1}+\frac{1}{x^{k-1}}\right)=u \cdot b_k - b_{k-1} $$

Answer 2

If you can do the case $p(x)=x^{2n-m}+x^{m}$ for each $m$ then you just take the right linear combination.

The special case is easily obtained by putting $x=\text{e}^{\text{i}\theta}$ and using the Chebychev polynomials of the first kind, $T_k$, which satisfy $T_k(\cos\theta)=\cos k\theta$ - you'll just need to sort out the powers of $2$.

(If you just want small explicit cases then do it recursively as @dxiv suggests).