Find the sum of $\binom{2016}{4} + \binom{2016}{8} +\binom{2016}{12} + \dots + \binom{2016}{2016}$ Problem:
Find 
$$\dbinom{2016}{4} + \dbinom{2016}{8} +\dbinom{2016}{12} + \dots + \dbinom{2016}{2016}$$
I don't know how to attempt this problem, other than that this sum is equivalent to finding the sum of the coefficients of degree 4 terms in the polynomial,
$$P(x) = (x+1)^{2016}$$
**I know that there's a duplicate of this problem somewhere, but I just can't find it on the website. Any help is appreciated!
 A: Hint:
Consider $(1+1)^{2016}+(1-1)^{2016}+(1+i)^{2016}+(1-i)^{2016}$
A: 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}$$.
A: $\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}
