Why is $\prod_{k=1}^m{(e^{ikx}+e^{-ikx})}=\sum_{\epsilon_{k}=\pm1}{e^{i(\epsilon_1+2\epsilon_2+\cdots+m\epsilon_m)x}}$ Problem A5 in the 1985 Putnam Competition: Let $I_m=\int_0^{2\pi}\cos(x)\cos(2x)\cdots\cos(mx)dx$. For which integers $m$, $1\leq m\leq10$, do we have $I_m\neq0$?
The solution rewrites $\cos(x)=\frac{e^{ikx}+e^{-ikx}}{2}$. It then says that $$I_m=\int_0^{2\pi}\prod_{k=1}^m{\biggl(\frac{e^{ikx}+e^{-ikx}}{2}\biggr)}=2^{-m}\sum_{\epsilon_{k}=\pm1}\int_0^{2\pi}{e^{i(\epsilon_1+2\epsilon_2+\cdots+m\epsilon_m)x}}$$
Where the sum ranges over the $2^m$ $m$-tuples $(\epsilon_1,\ldots,\epsilon_m)$ with $\epsilon_k=\pm1$ for every $k$. 
My question is, how do you make sense of the last step? Why is this true:
$$\prod_{k=1}^m{(e^{ikx}+e^{-ikx})}=\sum_{\epsilon_{k}=\pm1}{e^{i(\epsilon_1+2\epsilon_2+\cdots+m\epsilon_m)x}}$$
 A: 
We obtain
  \begin{align*}
\color{blue}{\prod_{k=1}^m}&\color{blue}{\left(e^{ikx}+e^{-ikx}\right)}\tag{1}\\
&=\prod_{k=1}^m\left(\sum_{\varepsilon_{k}=\pm  1}e^{i\varepsilon_{k}kx}\right)\\
&=\left(\sum_{\varepsilon_{1}=\pm 1}e^{i\varepsilon_1 x}\right)\left(\sum_{\varepsilon_{2}=\pm 1}e^{i\varepsilon_22 x}\right)
\cdots \left(\sum_{\varepsilon_{m}=\pm 1}e^{i\varepsilon_mm x}\right)\\
&=\sum_{\varepsilon_{1}=\pm 1}\sum_{\varepsilon_{2}=\pm 1}\cdots
\sum_{\varepsilon_{m}=\pm 1}e^{i\varepsilon_1 x}e^{i\varepsilon_22 x}\cdots e^{i\varepsilon_mm x}\\
&=\sum_{{1\leq k \leq m}\atop{\varepsilon_{k}=\pm 1}}e^{i\varepsilon_1 x}e^{i\varepsilon_22 x}\cdots e^{i\varepsilon_mm x}\\
&\,\,\color{blue}{=\sum_{{1\leq k \leq m}\atop{\varepsilon_{k}=\pm 1}}e^{i\left(\varepsilon_1 +2\varepsilon_2+\cdots +m \varepsilon_{m}\right)x}}\tag{2}
\end{align*}
  and the claim follows.

The product (1) consists of $m$ factors $e^{ikx}+e^{-ikx}$ where $1\leq k\leq m$. From each factor we select either $e^{ikx}$ or $e^{-ikx}$ giving a total of $2^m$ summands. These $2^m$ summands are explicitly stated in (2).
