I was doing a Putnam problem whose solution stated that $$\displaystyle \int_0^{2\pi}\prod_{k=1}^m \left(e^{ikx} + e^{-ikx}\right)dx = \sum_{e_k = \pm 1}\int_0^{2\pi}e^{ix(e_1+2e_2+...+me_m)}dx,$$ over all $2^m$ $m$-tuples $(e_1, e_2, ..., e_m)$.
Where exactly does this come from?
On
Attempt at a solution:
$$\newcommand{\e}{\mathrm{e}} \newcommand{\i}{\mathrm{i}} \cos z = \frac{\e^{\i z} + \e^{-\i z}}2$$
Substituting $z=kx$ gives
$$2\cos kx = \e^{\i kx} + \e^{-\i kx}$$
$$\begin{align} \prod_{k=1}^m \bigl(\e^{\i kx} + \e^{-\i kx}\bigr) &= \prod_{k=1}^m(2\cos kx) \\ &= 2\cos(x) \times 2\cos(2x) \times \cdots \times 2\cos(mx) \\ &= 2^m \cos(x)\cdots\cos(mx) \end{align}$$
While remembering $k$ stepped up as integers, slap that back into the integral:
$$2^m\int_0^{2π} \cos(x)\cdots\cos(mx) \, \mathrm dx$$
On the other side, you have your basic
$$\begin{align} \int_0^{2\pi}\e^{\i x(e_1+2e_2+...+me_m)}\,\mathrm dx &= \left.\frac1{\i(e_1+2e_2+...+me_m)} \, \e^{\i x(e_1+2e_2+...+me_m)}\right\rvert_{0}^{2π} \\[2ex] &= \frac{\cos 2πE + \i\sin 2πE - \cos 0 -\i\sin0}{\i E} \end{align}$$
I really don’t know what to do with that. Hope it gets the train of thought rolling.
It is really just an expansion of the product. Say $m=2$. Then $$(e^{i1x}+e^{-i1x})(e^{i2x}+e^{-i2x})=e^{ix(1+2)}+e^{ix(1-2)}+e^{ix(-1+2)}+e^{ix(-1-2)}$$ In the general case you need to add all terms $e^{ix(\pm1\pm2\pm3\pm...\pm m)}$