Power-reduction formula According to the Power-reduction formula, one can interchange between $\cos(x)^n$ and $\cos(nx)$ like the following:
$$
\cos^n\theta = \frac{2}{2^n} \sum_{k=0}^{\frac{n-1}{2}} \binom{n}{k} \cos{((n-2k)\theta)} \tag{odd}\\
$$
$$
\cos^n\theta = \frac{1}{2^n} \binom{n}{\frac{n}{2}} + \frac{2}{2^n} \sum_{k=0}^{\frac{n}{2}-1} \binom{n}{k} \cos{((n-2k)\theta)} \tag{even}
$$
To me this looks like an Binomial transform. Is this true?
May I think of it as a change of basis of a vector space?
 A: I don't know about the binomial transform, but you can get it from the binomial theorem after writing $\cos \theta = (e^{i\theta} + e^{-i\theta})/2$.
Yes, in the vector space of functions spanned by $\cos^j (\theta)$ for nonnegative integers $j$ it tells you how to transform to the basis $\cos(j \theta)$.
A: You can generalize your formulae for odd and even values of $n$. 
$$ \cos^n\theta = 2^{-n} \sum_{k=0}^n \bigl( \begin{smallmatrix} n \\ k \end{smallmatrix} \bigr) \cos (2k-n)\theta.$$
That looks nice and compact, but if you want to identify the individual cosines you'll need to add $\bigl( \begin{smallmatrix} n \\ k \end{smallmatrix} \bigr) \cos (-\alpha) + \bigl( \begin{smallmatrix} n \\ n-k \end{smallmatrix} \bigr) \cos \alpha = 2\bigl( \begin{smallmatrix} n \\ k \end{smallmatrix} \bigr) \cos \alpha $.
A: Yes, it's a binomial expansion:
$$
\begin{eqnarray}
\cos^n\theta
&=&
2^{-n}\left(\mathrm e^{\mathrm i\theta}+\mathrm e^{-\mathrm i\theta}\right)^n
\\
&=&
2^{-n}\sum_{k=0}^n\binom nk\mathrm e^{\mathrm ik\theta}\mathrm e^{-\mathrm i(n-k)\theta}
\\
&=&
2^{-n}\sum_{k=0}^n\binom nk\mathrm e^{\mathrm i(2k-n)\theta}\;,
\end{eqnarray}
$$
and then combining the terms whose exponents differ only by a sign (and whose coefficients coincide) yields the formulas you give. And yes, you may think of it as a change of basis if you wish, since both $\cos^n\theta$ and $\cos n\theta$ are linearly independent sets of functions; this is known from Fourier theory for $\cos n\theta$, and your transformation, which is clearly invertible,  shows that it's also true for $\cos^n\theta$.
