How can I find a short term for those sums?

Question

I have $A=[a_1,a_2,...,a_{2016}]$.
The number of subsets of $A$ where the number of elements is divisible by $4$, is $M$.
The number of subsets of $A$ where the number of elements is divisible by $2$ but not divisible by $4$, is $N$.
Find $M-N$.
Since $A$ contains $2016$ elements, the number of subsets where the number of elements is divisible by 4 is:
$$M=\sum_{n=0}^{504} {2016 \choose 4n} $$ Similarly, $$N=\sum_{n=1}^{504} {2016 \choose 4n-2}$$
Hence, $$M-N=\sum_{n=0}^{504} {2016 \choose 4n} - \sum_{n=1}^{504} {2016 \choose 4n-2} $$
How can I continue?
Thanks.

Answer 1

Use the following identity:

$$\binom{n}{t}+\binom{n}{t+s}+\binom{n}{t+2s}+\ldots=\frac{1}{s}\sum_{j=0}^{s-1}\left(2\cos\frac{\pi j}{s}\right)^n\cos\frac{\pi(n-2t)j}{s}$$

(for more details please refer to Series Multisection)

For $t=0$ and $s=4$ the identity becomes:

$$f(n)=\binom{n}{0} + \binom{n}{4}+\binom{n}{8}+\cdots = \frac{1}{2}\left(2^{n-1} +2^{\frac{n}{2}} \cos\frac{n\pi}{4}\right)$$

And for $t=2$ and $s=4$ the identity will be:

$$g(n)=\binom{n}{2} + \binom{n}{6}+\binom{n}{10}+\cdots = \frac{1}{2}\left(2^{n-1} -2^{\frac{n}{2}} \cos\frac{n\pi}{4}\right)$$

Obviously:

$$h(n)=f(n)-g(n)=2^{\frac{n}{2}} \cos\frac{n\pi}{4}$$

The result that you are looking for is:

$$h(2016)=2^{1008}\cos(504\pi)=2^{1008}$$

EDIT:

The following proof is elementary:

$$s=(1+i)^{2008}=\sum_{k=0}^{2008}\binom{2008}{k}i^k$$

$$\text{Real}(s)=\binom{2016}{0}i^0 + \binom{2016}{2}i^2 + \binom{2016}{4}i^4 + \binom{2016}{6}i^6 + ... + \binom{2016}{2014}i^{2014} + \binom{2016}{2016}i^{2016}$$

Note that $i^{4k}=1$ and $i^{4k+2}=-1$. With that in mind:

$$\text{Real}(s)=\binom{2016}{0} - \binom{2016}{2} + \binom{2016}{4} - \binom{2016}{6} + ... - \binom{2016}{2014} + \binom{2016}{2016}$$

$$\text{Real}(s)=\left(\binom{2016}{0} + \binom{2016}{4} + ... +\binom{2016}{2016}\right) - \left(\binom{2016}{2} + \binom{2016}{6} + ... +\binom{2016}{2014}\right)$$

This is exactly the number that you need.

On the other side:

$$s=(1+i)^{2016}=\left(\sqrt{2}(\cos\frac{\pi}{4}+i\sin\frac{\pi}{4})\right)^{2016}=2^{1008}(\cos\frac{2016\pi}{4}+i\sin\frac{2016\pi}{4})$$

Obviously:

$$\text{Real}(s)=2^{1008}\cos(504\pi)=2^{1008}$$

Same result as before, just more obvious.