# 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$?

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$.