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$.
 A: 
The $n$th sum is $\dfrac{2^n+2\cos(n\pi/3)}3$. Note that $2\cos(n\pi/3)$ is always in $\{-2,-1,1,2\}$ and, that, starting at $n=0$, it is $2$, $1$, $-1$, $-2$, $-1$, $1$, $2$, $1$, $-1$, $-2$, $-1$, $1$, $2$, $1$, etc.

To see why, use the third unit roots $$1,\qquad \mathrm j=\mathrm e^{2\mathrm i\pi/3},\qquad\mathrm j^2=\mathrm e^{-2\mathrm i\pi/3},$$ and that $1+\mathrm j^k+\mathrm j^{2k}=0$ for every $k$ except when $k$ is a multiple of $3$, and then $1+\mathrm j^k+\mathrm j^{2k}=3$. 
Thus, the sum $S_n$ to compute solves $$3S_n=\sum_k{n\choose k}(1+\mathrm j^k+\mathrm j^{2k})=\sum_k{n\choose k}+\sum_k{n\choose k}\mathrm j^k+\sum_k{n\choose k}\mathrm j^{2k},$$ that is, $$3S_n=(1+1)^n+(1+\mathrm j)^n+(1+\mathrm j^2)^n.
$$
Identifying $1+\mathrm j=\mathrm e^{\mathrm i\pi/3}$ and $1+\mathrm j^2=\mathrm e^{-\mathrm i\pi/3}$ allows to deduce that $$(1+\mathrm j)^n+(1+\mathrm j^2)^n=\mathrm e^{n\mathrm i\pi/3}+\mathrm e^{-n\mathrm i\pi/3}=2\cos(n\pi/3),
$$
which concludes the proof.
A: This technique is known as the Roots of Unity Filter. See this related question.
Note that $(1+x)^{n} = \displaystyle\sum_{k = 0}^{n}\dbinom{n}{k}x^k$. Let $\omega = e^{i2\pi/3}$. Then, we have:
$(1+1)^{n} = \displaystyle\sum_{k = 0}^{n}\dbinom{n}{k}1^k$
$(1+\omega)^{n} = \displaystyle\sum_{k = 0}^{n}\dbinom{n}{k}\omega^k$
$(1+\omega^2)^{n} = \displaystyle\sum_{k = 0}^{n}\dbinom{n}{k}\omega^{2k}$
Add these three equations together to get $\displaystyle\sum_{k = 0}^{n}\dbinom{n}{k}(1+\omega^k+\omega^{2k}) = 2^n+(1+\omega)^n+(1+\omega^2)^n$
You can see that $1+\omega^k+\omega^{2k} = 3$ if $k$ is a multiple of $3$ and $0$ otherwise.
Thus, $\displaystyle\sum_{m = 0}^{\lfloor n/3 \rfloor}\dbinom{n}{3m} = \dfrac{1}{3}\left[2^n+(1+\omega)^n+(1+\omega^2)^n\right]$
Now, simplify this.
A: If $1+\zeta+\zeta^2=0$, try to compute $(1+\zeta^0)^n + (1+\zeta)^n + (1+\zeta^2)^n$. Hint: $\zeta^3=1$, and, if $k$ is not divisible by $3$, $1+\zeta^k+\zeta^{2k}=0$.
A: I wanted to post this as a comment but it's not letting me, so please go easy on me.
Binomial coefficients are listed in Pascal's triangle, which suggests there is a recurrence relation for $\sum_{i = 0}^{\lceil \frac{n}{3} \rceil} \binom{n}{3i}$ and indeed there is. I looked in http://oeis.org/A024493 and found: $a(0) = 1$, $a(1) = 1$, $a(2) = 1$, $a(n) = 3a(n - 1) - 3a(n - 2) + 2a(n - 3)$.
A: $\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle}
 \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack}
 \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,}
 \newcommand{\dd}{{\rm d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}
 \newcommand{\fermi}{\,{\rm f}}
 \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}
 \newcommand{\half}{{1 \over 2}}
 \newcommand{\ic}{{\rm i}}
 \newcommand{\iff}{\Longleftrightarrow}
 \newcommand{\imp}{\Longrightarrow}
 \newcommand{\pars}[1]{\left(\, #1 \,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\pp}{{\cal P}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,}
 \newcommand{\sech}{\,{\rm sech}}
 \newcommand{\sgn}{\,{\rm sgn}}
 \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$
We can sum 'up to' $\ds{\infty\ \pars{~\mbox{Why ?}~}}$:

\begin{align}&\color{#66f}{\large\sum_{k = 0}^{\infty}{n \choose 3k}}
=\sum_{k = 0}^{\infty}\oint_{\verts{z}\ =\ a\ >\ 1}
{\pars{1 + z}^{n} \over z^{3k + 1}}\,{\dd z \over 2\pi\ic}
=\oint_{\verts{z}\ =\ a\ >\ 1}
{\pars{1 + z}^{n} \over z}\sum_{k = 0}^{\infty}\pars{1 \over z^{3}}^{k}
\,{\dd z \over 2\pi\ic}
\\[3mm]&=\oint_{\verts{z}\ =\ a\ >\ 1}
{\pars{1 + z}^{n} \over z}{1 \over 1 - 1/z^{3}}\,{\dd z \over 2\pi\ic}
=\oint_{\verts{z}\ =\ a\ >\ 1}
{\pars{1 + z}^{n}z^{2} \over z^{3} - 1}\,{\dd z \over 2\pi\ic}
\end{align}

$\ds{z^{3} - 1 = 0}$ has roots at $\ds{z_{m} = \expo{2m\pi\ic/3}\,,\ m = -1,0,1}$:
\begin{align}&\color{#66f}{\large\sum_{k = 0}^{\infty}{n \choose 3k}}
=\sum_{m = -1}^{1}\lim_{z\ \to\ z_{m}}
\bracks{\pars{z - z_{m}}\,{\pars{1 + z}^{n}z^{2} \over z^{3} - 1}}
=\sum_{m = -1}^{1}\bracks{{\pars{1 + z_{m}}^{n}z_{m}^{2} \over 3z_{m}^{2}}}
\\[3mm]&={1 \over 3}\sum_{m = -1}^{1}\pars{1 + z_{m}}^{n}
={1 \over 3}\braces{2^{n} + 2\,\Re\pars{\bracks{1 + \expo{2\pi\ic/3}}^{n}}}
\\[3mm]&={1 \over 3}\bracks{%
2^{n} + 2\,\Re\pars{\expo{-n\pi\ic/3}2^{n}\cos^{n}\pars{\pi \over 3}}}
=\color{#66f}{\large{1 \over 3}\bracks{2^{n} + 2\cos\pars{n\pi \over 3}}}
\end{align}
A: 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.
