Existence of polynomial such that $P_n(\cos\theta)=\cos(n\theta)$ Is there a way of proving existence of a polynomial $P_n(x)$ such that $\cos{(n\theta)}=P_n(\cos{\theta})$ without knowing the Chebyshev polynomials a priori?
 A: Induction: if $\cos n\theta=P_n(\cos\theta)$ then
$$\cos(n+1)\theta+\cos(n-1)\theta=2\cos n\theta\cos\theta$$
gives
$$P_{n+1}(x)=2xP_n(x)-P_{n-1}(x)\ .$$
A: $$\cos(n\theta) = \Re e^{ni \theta} = \Re(\cos(\theta)+i\sin(\theta))^n = Q(\cos(\theta),\sin^2(\theta)) = P(\cos(\theta))$$
$Q$ is a polynomial in $\cos(\theta)$ and $\sin^2(\theta)$ and $P$ is just a polynomial in $\cos(\theta)$.
A: I like user157227's basic line of attack which uses de Moivre's formula
$\cos n\theta + i\sin n\theta = (\cos \theta + i\sin \theta)^n, \tag{1}$
which itself may be seen as a consequence of Euler's formula
$e^{i\phi} = \cos \phi + i\sin \phi \tag{2}$
by choosing $\phi = n\theta$ and remembereing that $e^{in\theta} = (e^{i\theta})^n$; the only improvement I can offer, and I think it mos' def' is worth offering, is to add that the polynomial $\cos n \theta = Q_n(\cos \theta, \sin^2 \theta)$ may easily be explicitly presented by means of the binomial theorem applied to $(\cos \theta + i\sin \theta)^n$.  Indeed, we have
$(\cos \theta + i \sin \theta)^n = \sum_{k = 0}^n \dfrac{n!}{k!(n - k)!}(\cos \theta)^{n - k}(i\sin \theta)^k. \tag{3}$
From (1) we see that we only need the real part of (3) to find $\cos n \theta$, and this consists of the terms in (3) of even degree in $\sin \theta$: 
$\cos n \theta = \Re(\cos \theta + i \sin \theta)^n = \sum_{j = 0}^{\lfloor n/2 \rfloor} \dfrac{n!}{(2j)!(n - 2j)!}(\cos \theta)^{n - 2j}(i\sin \theta)^{2j}$
$= \sum_{j = 0}^{\lfloor n/2 \rfloor} (-1)^j\dfrac{n!}{(2j)!(n - 2j)!}(\cos \theta)^{n - 2j}(\sin^2 \theta)^j; \tag{4}$
thus we have an explicit formula for the polynomial $Q_n(\cos \theta, \sin^2 \theta) = \cos n \theta$.  Since $Q_n$ only contains $\sin \theta$ in the form $\sin^2 \theta$, we can use the identity $\sin^2 \theta = 1 - \cos^2 \theta$ to obtain a polynomial $P_n(\cos \theta)$ which only contains $\cos \theta$, and has no occurrence of $\sin \theta$:
$\cos n\theta = P_n(\cos \theta) = \sum_{j = 0}^{\lfloor n/2 \rfloor} (-1)^j\dfrac{n!}{(2j)!(n - 2j)!}(\cos \theta)^{n - 2j}(1 - \cos^2 \theta)^j. \tag{5}$
Hope this helps!  Cheers,
and as always,
Fiat Lux!!!
