How to prove that $\cos n \phi - \cos n \theta = 2^{n-1}\prod_{k=0}^{n-1}\left(\cos \phi - \cos\left(\theta - \frac{2k\pi}{n}\right)\right)$ 
Prove that $$\cos n \phi - \cos n \theta = 2^{n-1}\prod_{k=0}^{n-1}\left(\cos \phi - \cos\left(\theta - \frac{2k\pi}{n}\right)\right)$$
where $n \in \mathbb{Z^+} $ and $k \in \{0, 1, \dots ,n - 1\}$

My first instinct is to multiply both sides by $2$ to make $2^{n-1}$ on RHS to be $2^n$ and distribute it inside the product. However, I can't simplify it further after reaching $2(\cos n\phi - \cos n\theta) = \prod_{k=0}^{n-1} 4\sin\frac{\phi-\theta-\frac{2k\pi}{n}} {2}\sin\frac{\phi+\theta+\frac{2k\pi}{n}}{2}$.
I think that De Moivre's theorem would be useful here. However, I don't see how I could use that in the first place. How should I solve this question? Thanks in advance.
 A: Just as hinted in the comments, you can use the $n$-th Chebyshev's polynomial:
$$\forall\phi\in\mathbb{R},\:T_n(\cos\phi)=\cos n\phi.$$
So you wish to show the following identity:
$$T_n(\cos\phi)-\cos n\theta=2^{n-1}\prod_{k=0}^{n-1}\left(\cos\phi-\cos\left(\theta-\frac{2k\pi}{n}\right)\right)$$
This expression is polynomial in $\cos\phi$ so our goal is to show that
$$T_n(X)-\cos n\theta=2^{n-1}\prod_{k=0}^{n-1}\left(X-\cos\left(\theta-\frac{2k\pi}{n}\right)\right)$$
They are both of degree $n$ and have dominating coefficient $2^{n-1}$.
Special Case: We suppose that $\theta\notin\frac{\pi}{n}\mathbb{Z}$.
We now show they have the same roots: for every $k\in\{0,1,\ldots,n-1\}$ $\cos\left(\theta-\frac{2k\pi}{n}\right)$ is a root of the polynomial on the RHS and
$$T_n\left(\cos\left(\theta-\frac{2k\pi}{n}\right)\right)-\cos n\theta=
\cos n\left(\theta-\frac{2k\pi}{n}\right)-\cos n\theta=\cos(n\theta-2k\pi)-\cos n\theta=0.$$
Now the assumption $\theta\notin\frac{\pi}{n}\mathbb Z$ ensures that the roots $\cos\left(\theta-\frac{2k\pi}{n}\right),\:k=0,1,\ldots,n-1$ are all distinct, thus the two expressions are equal.
General case: we now assume general $\theta$. If it falls in the previous case, then we are done, if not, then some of the $\cos\left(\theta-\frac{2k\pi}{n}\right)$ may turn out to be multiple roots. In order to make use of the first case, we simply perturb $\theta$ by a small amount $\epsilon>0$ so that it is not in $\frac{\pi}{n}\mathbb Z$. The coefficients of both polynomials we wish to show are equal, are  continuous functions in $\theta$, then, since for all small $\epsilon$ the two polynomials are equal:
$$\forall\epsilon>0,\epsilon\ll 1,\:T_n(X)-\cos n(\theta+\epsilon)=2^{n-1}\prod_{k=0}^{n-1}\left(X-\cos\left(\theta+\epsilon-\frac{2k\pi}{n}\right)\right),$$
by making $\epsilon\to0$, we will obviously get our desired identity.
