# Substitution in Palindromic Polynomial

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$.

• Are you sure you wrote correctly your formula? Left side isn't a polynomial Dec 22, 2017 at 17:43
• @JohnWatson I'm sorry you're right. It's the wrong way around.
– Jiro
Dec 22, 2017 at 17:46

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}$$

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).

• Nice, I'm actually interested in the special case. I'm missing though the connection to the Chebychev polynomials.
– Jiro
Dec 22, 2017 at 18:36
• @SebastianSchlecht Chebyshev polynomials satisfy $\,T_{n+1} = 2x\, T_n - T_{n-1}\,$ which is similar to $\,b_{k+1}=x\,b_k-b_{k-1}\,$ from my answer. However, I don't immediately see how to "sort out" that extra factor of $\,2\,$, and also get the initial conditions to match.
– dxiv
Dec 22, 2017 at 20:08