<s>[INST] sum of combinations $\binom n{0} + \binom n{3} + \binom n{6} +... +\binom n{3k}$ How should one prove that $\binom n{0} + \binom n{3} + \binom n{6} +... +\binom n{3k} = \dfrac{2^n-2}{3}$ for $n$ odd and $\binom n{0} + \binom n{3} + \binom n{6} +... +\binom n{3k} = \dfrac{2^n+2}{3}$ for $n$ even, where $k=\lfloor \dfrac{n}{3}\rfloor $?
 [/INST] Hint: consider
$$
(1+x)^n = \sum_{k = 0}^n \binom nk x^k
$$
for $x\in \{1,j,j^2\} \ \ \ (j^3 = 1, j\notin \Bbb R)$ and $1 + j + j^2 = 0$.
</s>