Write $\cos(n \theta)$ as a combination of powers of $\cos(\theta)$ with integer coefficients. I am trying to show that $\cos(n \theta) = \sum C_n \cos^n(\theta) $ where $C_n \in \mathbb{C}$.
I know that :
$$ \cos(n \theta) + i\sin(n\theta) = (\cos(\theta) + i\sin(\theta))^n = \sum {n \choose k} (\cos( \theta))^{n-k} (i \sin( \theta))^k$$
$$ \cos(n \theta) - i\sin(n\theta) = (\cos(\theta) - i\sin(\theta))^n = \sum {n \choose k} (\cos( \theta))^{n-k} (-i \sin( \theta))^k$$
Summing here allows you to have an expression for $2 \cos(n \theta)$, but I am not sure what guarantees the sine components to be integers? A hint would be appreciated.
 A: Conrad's suggestion in the comments works great and is probably the most low-tech solution. Here are some others. Write $z = e^{i \theta}$, so the question is to show that $z^n + z^{-n}$ is a polynomial in $z + z^{-1}$. These are Laurent polynomials (polynomials in $z$ and $z^{-1}$).

*

*Consider the vector space of Laurent polynomials $f(z)$ containing terms between $z^{-n}$ and $z^n$ and satisfying $f(z) = f(z^{-1})$. It's not hard to see that $\{ z^k + z^{-k} : 0 \le k \le n \}$ is a basis for this vector space, so it has dimension $n+1$. On the other hand, $\{ (z + z^{-1})^k : 0 \le k \le n \}$ is also a basis (e.g. because it consists of polynomials of different degrees so is linearly independent, and has size $n + 1$). So there must be a change-of-basis matrix relating the two.


*We have $(z + z^{-1})^n = \sum_{k \ge 0} {n \choose k} z^{n-2k}$, which shows that $(\cos \theta)^n$ can be written as a linear combination of $\cos k \theta, 0 \le k \le n$ such that the coefficient of $\cos n \theta$ is $1$. This gives a triangular matrix relating the sequences of functions $\cos^n \theta$ and $\cos n\theta$ with $1$s on the diagonal, and all such matrices have an inverse which is another such matrix. It follows that $\cos n \theta$ is a monic polynomial in $\cos \theta$ of degree $n$. This is basically a somewhat more explicit variant of the first argument.


*Consider the generating function $\sum_{n \ge 0} (z^n + z^{-n}) t^n = \frac{1}{1 - zt} + \frac{1}{1 - z^{-1} t}$. Adding these fractions gives $\frac{2 - (z + z^{-1}) t}{1 - (z + z^{-1}) t + t^2}$ and expanding this out produces a generating function in $t$ whose coefficients are polynomials in $z + z^{-1}$.
That last expression is, up to a factor of $2$, the generating function of the Chebyshev polynomials of the first kind $T_n$, the polynomials satisfying $\cos n \theta = T_n(\cos \theta)$ we've been trying to find, as mentioned by Jean Marie in the comments. Much is known about them and they have lots of interesting properties.
Overall I'd summarize the thrust of all the above arguments as saying that the vector space of Laurent polynomials satisfying $f(z) = f(z^{-1})$ (one might call them symmetric) has a basis given by any sequence $f_n(z)$ of symmetric Laurent polynomials of degree $n$.
Edit: Ah, I didn't see that the title asks for integer coefficients (the body only asks for complex coefficients). The first argument, as written, only provides rational coefficients, but the other two provide integer coefficients; the inverse of a triangular matrix with $1$s on the diagonal involves no divisions, so for an integer such matrix the inverse also consists of integers. The generating function expansion also involves no divisions. The general statement above about Laurent polynomials is still true over $\mathbb{Z}$ if one adds the adjective "monic."
A: Prove more: For all positive integers $n$,
$$
\cos(n\theta) = T_n(\cos(\theta)),
\qquad \sin(n\theta) = \sin(\theta) U_{n-1}(\cos\theta)
$$
where $T_n(x)$ and $U_{n-1}(x)$ are polynomials with integer coefficients.
Prove it by induction.
$$
\cos(1\theta) = \cos(\theta) = T_1(\cos(\theta)),\quad
\sin(1\theta) = \sin(\theta) = \sin(\theta)U_0(\cos(\theta)),
$$
where $T_1(x) = x$ and $U_0(x) = 1$ are polynomials with integer coefficients.
Let $n \ge 1$ and assume $\cos(n\theta) = T_n(\cos(\theta))$
and $\sin(n\theta) = \sin(\theta)U_{n-1}(\cos(\theta))$,
where $T_n(x)$ and $U_{n-1}(x)$ are a polynomials with integer coefficients.  Then for $n+1$ we have
\begin{align}
\cos((n+1)\theta) &= \cos(n\theta)\cos(\theta) - \sin(n\theta)\sin(\theta)
\\ &= T_n(\cos(\theta)\cos(\theta) - \sin^2(\theta)U_{n-1}(\cos(\theta))
\\ &=T_{n+1}(\cos(\theta)),
\end{align}
where $T_{n+1}(x) = xT_n(x)-(1-x^2)U_{n-1}(x)$ is a polynomial with integer coefficients; and
\begin{align}
\sin((n+1)\theta) &= \sin(n\theta)\cos(\theta)+\cos(n\theta)\sin(\theta)
\\ &= \sin(\theta)U_{n-1}(\cos(\theta))\cos(\theta)
+T_n(\cos(\theta))\sin(\theta)
\\ &=\sin(\theta) U_n(\cos(\theta)),
\end{align}
where $U_n(x) = U_{n-1}(x)x + T_n(x)$ is a polynomial with integer coefficients.

If you need a formula for the coefficients ... see references on "Chebyshev polynomials".
