number of $k$-subsets of an $n$ element set, where $k \equiv 1 \bmod 3$

Question

I would like to find the number of $k$-subsets of an $n$ element set, where $k \equiv 1\bmod 3$.

We can consider the set $[n]=\{1,2, \ldots, n\}$. The number I am looking for would be

$$\sum_{j\geq 0} \binom{n}{3j+1}.$$

Is there a well known closed formula for this sum? Thank you!

Answer 1

Count subsets whose cardinalities are congruent to 0, 1 and 2 modulo 3 respectively (couldn't put this as comment because I don't have sufficient reputation).

Answer 2

I think you should try using complex number. For instance, let

$$P(x)=(1+x)^n$$

then

$$\sum_{j\geq 0}\binom{n}{3j+1}=\frac{1}{3}\left(\omega^2P(\omega)+\omega P(\omega^2)+2^n\right)$$ where $\omega=e^{\frac{2\pi i}{3}}=-\frac12+\frac12\sqrt{3}$.