Proving that $x^m+x^{-m}$ is a polynomial in $x+x^{-1}$ of degree $m$.

Question

I need to prove, that $x^m+x^{-m}$ is a polynomial in $x+x^{-1}$ of degree $m$.

---

Prove that $$x^m+x^{-m}=P_m (x+x^{-1} )=a_m (x+x^{-1} )^m+a_{m-1} (x+x^{-1} )^{m-1}+\cdots+a_1 (x+x^{-1} )+a_0$$ on induction in $m$.

1. $m=1$;
2. $m=k$;
3. $⊐n=k+1$. Than $$x^{k+1}+x^{-k-1}=(x+x^{-1} )^{k+1} + (x+x^{-1} )^{k}+ (x+x^{-1} )^{k-1}+\cdots+(x+x^{-1} ).$$

I stuck on step 3. How to prove this expression?

Answer 1

Let $y=x+x^{-1}$. We show by strong induction that if $n$ is a non-negative integer, then $x^n+x^{-n}$ is a polynomial of degree $n$ in $y$. It is easy to verify that the result holds for $n=0$ and $n=1$. We now show that if the result holds for all $n\le k$, then the result holds for $n=k+1$.

We have $$x^{k+1}+x^{-(k+1)}=(x^k+x^{-k})(x+x^{-1})-(x^{k-1}+x^{-(k-1)}).\tag{1}$$ By the induction hypothesis, $x^k+x^{-k}$ is a polynomial of degree $k$ in $y$. So $(x^k+x^{-k})(x+x^{-1})$ is a polynomial of degree $k+1$ in $y$. Also by the induction hypothesis, $x^{k-1}+x^{-(k-1)}$ is a polynomial of degree $k-1$ in $y$. It follows from (1) that $x^{k+1}+x^{-(k+1)}$ is a polynomial of degree $k+1$ in $y$.

Answer 2

$$\cos m \theta = T_m(\cos \theta)$$ with $T_m$ the Chebyshev polynomial of first kind, so, taking $x = e^{i\theta}$ $$x^{m} + x^{-m} = P_m(x+ x^{-1})$$ where $P_m(t) = 2 T_m(\frac{t}{2})$. For instance $$x^{12} + x^{-12}= P_{12}(x+x^{-1})$$ where $P_{12}(t) = t^{12}-12 t^{10}+54 t^8-112 t^6+105 t^4-36 t^2+2$.