<s>[INST] Finding $\binom{n}{0} + \binom{n}{3} + \binom{n}{6} + \ldots $ Help me to simplify:$$\binom{n}{0} + \binom{n}{3} + \binom{n}{6} + \ldots $$
I got a hunch that it will depend on whether $n$ is a multiple of $6$ and equals to $\frac{2^n+2}{3}$ when $n$ is a multiple of $6$.
 [/INST] Here's a method that doesn't (explicitly) involve complex numbers.
Let $A_n=\sum_k \binom{n}{3k}$, $B_n=\sum_k \binom{n}{3k+1}$, $C_n=\sum_k \binom{n}{3k+2}$.
Then $A_n+B_n+C_n=2^n$ by the binomial theorem. Moreover, Pascal's identity implies the following:
$$
\begin{eqnarray}
A_n&=&A_{n-1} + C_{n-1} =2^{n-1}-B_{n-1} \\
B_n&=&B_{n-1} + A_{n-1} = 2^{n-1}-C_{n-1} \\
C_n&=&C_{n-1} + B_{n-1} = 2^{n-1}-A_{n-1}
\end{eqnarray}
$$
Putting all these together, 
$$A_n = 2^{n-1}-(2^{n-2} - C_{n-2})=2^{n-2} + C_{n-2} = 2^{n-2} + 2^{n-3} - A_{n-3} = 3(2^{n-3}) - A_{n-3} \, .$$ 
Also, $A_0=A_1=A_2=1$.
It follows that $A_{3n}=3(2^{n-3}-2^{n-6}+\dots \pm 2^0) \mp 1$, with similar expressions for $A_{3n+1}$ and $A_{3n+2}$. Obviously, you could use a geometric series formula to further simplify this.
</s>