More fun in 2016, Part 1

This problem is a simple example of a beautiful and important method called "roots of unity filter," a special case of the discrete Fourier transform. Let me try to provide some background.

Consider a polynomial $f(x)=a_0+a_1x+...+a_nx^n$ . Then $f(1)$ is the sum of all the coefficients, and $\frac{f(1)+f(-1)}{2}$ is the sum of all coefficients $a_k$ with an even $k$ . More generally, if $w$ is a primitive $m$ th root of unity, then $\frac{f(1)+f(w)+f(w^2)+...+f(w^{m-1})}{m}$ is the sum of all coefficients of the form $a_{km}$ ... we are "filtering out" the coefficients of this form. To understand how this filter works, take a look at this post .

Now consider $f(x)=(x+1)^{2016}=\sum_{k=0}^{2016}{2016 \choose k}x^k$ . To "filter out" $\sum_{k=0}^{672}{2016 \choose 3k}$ , consider $\frac{1}{3}(f(1)+f(\omega)+f(\omega^2))$ $=\frac{1}{3}(2^{2016}+(1+\omega)^{2016}+(1+\omega^2)^{2016})$ $=\frac{1}{3}(2^{2016}+(-\omega^2)^{2016}+(-\omega)^{2016})$ $=\frac{1}{3}(2^{2016}+2$ ) since $2016$ is divisible by 3.

I will leave it as an exercise to the interested reader to find $\sum_{k=0}^{\lfloor{n/3}\rfloor}{n \choose 3k}$ for arbitrary $n$ .

We know that $(1+x)^n = \displaystyle \sum_{k=0}^{n} \begin{pmatrix} n \\ k \end{pmatrix} x^k$ , therefore:

$\begin{aligned} (1+x)^{2016} & = \small \begin{pmatrix} 2016 \\ 0 \end{pmatrix} + \begin{pmatrix} 2016 \\ 1 \end{pmatrix} x + \begin{pmatrix} 2016 \\ 2 \end{pmatrix} x^2 + \begin{pmatrix} 2016 \\ 3 \end{pmatrix} x^3 + \begin{pmatrix} 2016 \\ 4 \end{pmatrix} x^4 +...+ \begin{pmatrix} 2016 \\ 2016 \end{pmatrix} x^{2016} \\ \Rightarrow (1+1)^{2016} & = \small \begin{pmatrix} 2016 \\ 0 \end{pmatrix} + \begin{pmatrix} 2016 \\ 1 \end{pmatrix} + \begin{pmatrix} 2016 \\ 2 \end{pmatrix} + \begin{pmatrix} 2016 \\ 3 \end{pmatrix} + \begin{pmatrix} 2016 \\ 4 \end{pmatrix} +...+ \begin{pmatrix} 2016 \\ 2016 \end{pmatrix} \\ \Rightarrow (1+e^{i\frac{2\pi}{3}})^{2016} & = \small \begin{pmatrix} 2016 \\ 0 \end{pmatrix} + \begin{pmatrix} 2016 \\ 1 \end{pmatrix} e^{i\frac{2\pi}{3}} + \begin{pmatrix} 2016 \\ 2 \end{pmatrix} e^{i\frac{4\pi}{3}} + \begin{pmatrix} 2016 \\ 3 \end{pmatrix} e^{i 2\pi} + \begin{pmatrix} 2016 \\ 4 \end{pmatrix} e^{i\frac{8\pi}{3}} +...+ \begin{pmatrix} 2016 \\ 2016 \end{pmatrix} e^{i 448\pi} \\ & = \small \begin{pmatrix} 2016 \\ 0 \end{pmatrix} + \begin{pmatrix} 2016 \\ 1 \end{pmatrix} \left(\cos \frac{2\pi}{3} + i\sin \frac{2\pi}{3} \right) + \begin{pmatrix} 2016 \\ 2 \end{pmatrix} \left(\cos \frac{4\pi}{3} + i\sin \frac{4\pi}{3} \right) \\ & \small \quad \quad + \begin{pmatrix} 2016 \\ 3 \end{pmatrix} \left(\cos 2\pi + i\sin 2\pi \right) + \begin{pmatrix} 2016 \\ 4 \end{pmatrix} \left(\cos \frac{8\pi}{3} + i\sin \frac{8\pi}{3} \right) +...+ \begin{pmatrix} 2016 \\ 2016 \end{pmatrix} \left(\cos 448\pi + i\sin 448\pi \right) \\ & = \small \begin{pmatrix} 2016 \\ 0 \end{pmatrix} + \begin{pmatrix} 2016 \\ 1 \end{pmatrix} \left(-\frac{1}{2} + i\frac{\sqrt{3}}{2} \right) + \begin{pmatrix} 2016 \\ 2 \end{pmatrix} \left(-\frac{1}{2} - i\frac{\sqrt{3}}{2} \right) + \begin{pmatrix} 2016 \\ 3 \end{pmatrix} \left(1 + i 0 \right) \\ & \small \quad \quad + \begin{pmatrix} 2016 \\ 4 \end{pmatrix} \left(-\frac{1}{2} + i\frac{\sqrt{3}}{2} \right) +...+ \begin{pmatrix} 2016 \\ 2016 \end{pmatrix} \left(1+ i0 \right) \\ \Rightarrow \Re (1+e^{i\frac{2\pi}{3}})^{2016} & = \small \begin{pmatrix} 2016 \\ 0 \end{pmatrix} - \frac{1}{2} \begin{pmatrix} 2016 \\ 1 \end{pmatrix} - \frac{1}{2} \begin{pmatrix} 2016 \\ 2 \end{pmatrix} + \begin{pmatrix} 2016 \\ 3 \end{pmatrix} - \frac{1}{2} \begin{pmatrix} 2016 \\ 4 \end{pmatrix} -...+ \begin{pmatrix} 2016 \\ 2016 \end{pmatrix}\end{aligned}$

Therefore, we can see that:

$\begin{aligned} S & = \sum_{k=0}^{672} \begin{pmatrix} 2016 \\ 3k \end{pmatrix} \\ & = \frac{(1+1)^{2016} + 2 \Re \left[\left(1+e^{i\frac{2\pi}{3}}\right)^{2016} \right]}{3} \\ & = \frac{2^{2016} + 2 \Re \left[\left(1-\frac{1}{2} + i \frac{\sqrt{3}}{2} \right)^{2016} \right]}{3} \\ & = \frac{2^{2016} + 2 \Re \left[\left( e^{i\frac{\pi}{3}} \right)^{2016} \right]}{3} \\ & = \frac{2^{2016} + 2 \Re \left[e^{i 672 \pi} \right]}{3} \\ & = \frac{2^{2016} + 2(1)}{3} \\ & \\ \Rightarrow a & = \boxed{2} \end{aligned}$

$\color{#3D99F6}{\text{For generalization:}}$

Thanks Otto for introducing the "Roots of Unity Filter". I solved the problem without knowing this simple approach. Now, I am solving the bonus generalization with its use.

$\begin{aligned} S & = \sum_{k=0}^{\left \lfloor \frac{n}{3} \right \rfloor} \begin{pmatrix} n \\ 3k \end{pmatrix} \\ & = \frac{1}{3} \left(f(1) + f(\omega) + f(\omega^2) \right) \\ & = \frac{1}{4} \left(2^n + (-\omega^2)^n + (-\omega)^n \right) \\ & = \frac{1}{4} \left(2^n + (-1)^n(\omega^n + \omega^{2n}) \right) \\ & = \begin{cases} \dfrac{2^n + (-1)^n(2)}{4} & \text{for } 3 \mid n \\ \dfrac{2^n + (-1)^{n+1}}{4} & \text{for } 3 \nmid n \end{cases} \end{aligned}$