Find the sum of $\binom{2016}{4} + \binom{2016}{8} +\binom{2016}{12} + \dots + \binom{2016}{2016}$

Hint:

Consider $(1+1)^{2016}+(1-1)^{2016}+(1+i)^{2016}+(1-i)^{2016}$

It turns out to be marginally cleaner to deal with a sum that is the same as your sum, except including ${2016 \choose 0} = 1$ as well. That's what I'll do.

Consider the polynomial

$$P_n(x) = {(1+x)^n + (1+ix)^n + (1-x)^n + (1-ix)^n \over 4}$$

and determine the coefficient of $x^k$ in this polynomial. For example, the coefficient of $x^1$ is

$$[x^1] P_n(x) = {1 \over 4} \left( {2016 \choose 1} + i {2016 \choose 1} - {2016 \choose 1} - i {2016 \choose 1} \right)$$

where I have used the very useful notation $[x^k] P(x)$ for the coefficient of $x^k$ in a polynomial or power series $P(x)$. Since $1 + i - 1 - i = 0$, that's zero. You can similarly see that the coefficients of $x^2$ and $x^3$ will be zero. In fact, more generally, the coefficient of $x^k$ in $P_n(x)$ is

$$[x^k] P_n(x) = {1 \over 4} \left( 1^k {n \choose k} + i^k {n \choose k} + (-1)^k {n \choose k} + (-i) {n \choose k} \right) $$

and factoring gives

$$[x^k] P_n(x) = {n \choose k} {1^k + i^k + (-1)^k + (-i)^k \over 4}.$$

You can check, by looking at the different cases modulo 4, that this is just ${2016 \choose k}$ if $k$ is divisible by 4, and 0 otherwise.

But a polynomial is just the sum of its coefficients, so you have

$$P_n(x) = \sum_{k=0}^n [x^k] P_n(x) = \sum_{4|k} {n \choose k} x^k $$

and set $x = 1, n = 2016$ to get

$$P_{2016}(1) = \sum_{4|k} {2016 \choose k}.$$

But now recall how $P_n(x)$ was defined - you get

$$P_{2016}(1) = {2^{2016} + (1+i)^{2016} + 0^{2016} + (1-i)^{2016} \over 4}.$$

This is a bit annoying to deal with! But observe that $(1+i)^8 = (1-i)^8 = 2^4$, and so finally you have

$$P_{2016}(1) = {2^{2016} + 2 \times 2^{2016/2} \over 4}$$.

$\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} \sum_{n = 1}^{504}{2016 \choose 4n} & = -1 + \sum_{n = 0}^{2016}{2016 \choose n} {1 + \pars{-1}^{n} + \ic^{n} + \pars{-\ic}^{n} \over 4} \\[5mm] & = -1 + {1 \over 4}\sum_{n = 0}^{2016}{2016 \choose n} + {1 \over 4}\sum_{n = 0}^{2016}{2016 \choose n}\pars{-1}^{n} \\[2mm] & + {1 \over 2}\,\Re\sum_{n = 0}^{2016}{2016 \choose n}\ic^{n} \\[5mm] & = -1 + {1 \over 4}\,\pars{1 + 1}^{2016}+ {1 \over 4}\,\pars{1 - 1}^{2016} + {1 \over 2}\,\Re\pars{1 + \ic}^{2016} \\[5mm] & = -1 + 2^{2014} + {1 \over 2}\,\Re\pars{2^{1008}\expo{504\pi\ic}} = \bbx{\ds{-1 + 2^{2014} + 2^{1007}}} \end{align}