Proving that $x^m+x^{-m}$ is a polynomial in $x+x^{-1}$ of degree $m$. 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$.


*

*$m=1$;

*$m=k$;

*$⊐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?
 A: 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$.
A: $$\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$.
