Yet Another Ode To 2016

A quick summary of a possible solution ....

Essentially what we're looking for is the sum of the coefficients of the polynomial $f(x) = (1 + x)^{2016}$ for all powers of $x$ that are divisible by $3$ . By way of the roots of unity filter, (discussion below), we just then need to evaluate

$\dfrac{f(1) + f(\omega) + f(\omega^{2})}{3}$ where $\omega = \large e^{i\frac{2\pi}{3}}$ .

Since $\omega^{2} + \omega + 1 = 0$ this then comes out to

$\dfrac{2^{2016} + (1 + \omega)^{2016} + (1 + \omega^{2})^{2016}}{3} = \dfrac{2^{2016} + (-\omega^{2})^{2016} + (-\omega)^{2016}}{3} = \dfrac{2^{2016} + 2}{3}$ .

Thus $a + b + c + d = 2 + 2016 + 2 + 3 = \boxed{2023}$ .

Roots of unity filter: Start with the generating function $f(x) = (1 + x)^{n} = \displaystyle\sum_{k=0}^{n} \dbinom{n}{k}x^{k}$ .

Now for $\omega = \large e^{i\frac{2\pi}{3}}$ we observe that $1 + \omega^{k} + \omega^{2k} = 3$ if $3|k$ and equals $0$ otherwise. This "filtering" process allows us to conclude that

$\displaystyle\sum_{k=0}^{\lfloor \frac{n}{3} \rfloor} \dbinom{n}{3k} = \dfrac{f(1) + f(\omega) + f(\omega^{2})}{3}$ ,

from which we can continue as outlined in the above solution. (A similar method can be used when the summation involves $\binom{n}{mk}$ for $m$ other than $3$ , with $\large \omega = e^{i\frac{2\pi}{m}}$ .)

Let $n$ be a positive integer. My equation is as followed. \sum_{k=0}^{n} \binom{3n}{3k} = \left\{ \begin{array}{11} \frac{2^{3n} - 2}{3} & \text{if } n \text{ is odd} \\ \frac{2^{3n} + 2}{3} & \text{if } n \text{ is even} \end{array}\right.

This can be proven by induction which I leave as an exercise. To prove it, note that $\sum_{k=0}^{n} \binom{n}{k} = (1+1)^n = 2^n$ and also $\sum_{k=0}^{n-1} \binom{3n}{k+1} = \sum_{k=0}^{n-1} \binom{3n}{k+2}$ which can be shown by symmetry.