<s>[INST] Closed Formula Expression for Sum of Combinatorics I have recently been interested in the problem of summing Combinatorials. I have been beating my brain for the past days to figure out how to find an explicit closed form of:
$n \choose 0 $+$ n \choose 3 $+$ n \choose 6$ + $\dots$ + $n \choose 3K$, where $3K$ is the largest multiple of $3$ less than or equal to $n$.
I have tried the expansion of $(1+1+1)^n$ which got nowhere, and I dont know how to proceed. I figure the answer will be conditional on $n \pmod 6$.
Can someone lend help? Thank you.
 [/INST] Let $\omega$ be a third root of 1.
Then
$$(1+1)^n = \binom{n}{0} +\binom{n}{1}+  \binom{n}{2}+ \binom{n}{3}+ ...+\binom{n}{n} \,.$$
$$ (1+\omega)^n = \binom{n}{0} + \binom{n}{1}\omega+ \binom{n}{2} \omega^2+ \binom{n}{3}+ ...+ \binom{n}{n} \omega^n \,.$$
$$ (1+\omega^2)^n =\binom{n}{0} + \binom{n}{1} \omega^2+  \binom{n}{2} \omega+ \binom{n}{3}+ ...+ \binom{n}{n}\omega^{2n} \,.$$
Now, since $1+ \omega +\omega^2=0$, adding them only every third column remains.
Thus
$$2^n+ (1+\omega)^n+(1+\omega^2)^n =3 \left( \binom{n}{0} +\binom{n}{3}+  \binom{n}{6}+ \binom{n}{9}+ ...+\binom{n}{3k} \right)$$
All you have left is to calculate $(1+\omega)^n$ and $(1+\omega^2)^n$ by writing them in polar/trig form.
P.S.  Same trick with $\omega(1+\omega)^n$ and $\omega^2 (1+\omega^2)^n$ yields  $\left( \binom{n}{2} +\binom{n}{5}+  \binom{n}{8}+ \binom{n}{11}+ ... \right)$ while $\omega^2(1+\omega)^n$ and $\omega (1+\omega^2)^n$ yields  $\left( \binom{n}{1} +\binom{n}{4}+  \binom{n}{7}+ \binom{n}{10}+ ... \right)$.
</s>