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

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

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