Show that $\sum_{k=0}^n\binom{3n}{3k}=\frac{8^n+2(-1)^n}{3}$ The other day a friend of mine showed me this sum: $\sum_{k=0}^n\binom{3n}{3k}$. To find the explicit formula I plugged it into mathematica and got $\frac{8^n+2(-1)^n}{3}$. I am curious as to how one would arrive at this answer.
My progress so far has been limited. I have mostly been trying to see if I can somehow relate the sum to $$\sum_{k=0}^{3n}\binom{3n}{k}=8^n$$ but I'm not getting very far. I have also tried to write it out in factorial form, but that hasn't helped me much either.
How would I arrive at the explicit formula?
 A: It can be proved fairly straightforwardly by induction.
Let $S_0(n)=\sum_{k\ge 0}\binom{3n}{3k}$, $S_1(n)=\sum_{k\ge 0}\binom{3n}{3k+1}$, and $S_2(n)=\sum_{k\ge 0}\binom{3n}{3k+2}$; then $$S_0(n)+S_1(n)+S_2(n)=\sum_{k\ge 0}\binom{3n}k=2^{3n}=8^n\;.$$
Now 
$$\begin{align*}
S_0(n)&=\sum_{k\ge 0}\binom{3n}{3k}\\
&=\sum_{k\ge 0}\left(\binom{3n-3}{3k-3}+3\binom{3n-3}{3k-2}+3\binom{3n-3}{3k-1}+\binom{3n-3}{3k}\right)\\
&=\sum_{k\ge 0}\left(\binom{3n-3}{3k-3}+\binom{3n-3}{3k-2}+\binom{3n-3}{3k-1}\right)\\
&\qquad\qquad+\sum_{k\ge 0}\left(\binom{3n-3}{3k-2}+\binom{3n-3}{3k-1}+\binom{3n-3}{3k}\right)\\
&\qquad\qquad+\sum_{k\ge 0}\left(\binom{3n-3}{3k-2}+\binom{3n-3}{3k-1}\right)\\
&=S_0(n-1)+S_1(n-1)+S_2(n-1)\\
&\qquad\qquad+S_0(n-1)+S_1(n-1)+S_2(n-1)\\
&\qquad\qquad+S_1(n-1)+S_2(n-1)\\
&=3\cdot8^{n-1}-S_0(n-1)\\
&=3\cdot8^{n-1}-\frac{8^{n-1}+2(-1)^{n-1}}3\qquad\qquad\text{by the induction hypothesis}\\
&=\frac{8^n-2(-1)^{n-1}}3\\
&=\frac{8^n+2(-1)^n}3\;.
\end{align*}$$
A: $\newcommand{\+}{^{\dagger}}
 \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{\down}{\downarrow}
 \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{\isdiv}{\,\left.\right\vert\,}
 \newcommand{\ket}[1]{\left\vert #1\right\rangle}
 \newcommand{\ol}[1]{\overline{#1}}
 \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{\ul}[1]{\underline{#1}}
 \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}
 \newcommand{\wt}[1]{\widetilde{#1}}$
$$
\mbox{Note that}\quad\sum_{k = 0}^{n}{3n \choose 3k}
=\sum_{k = 0}^{\infty}{3n \choose 3k}
$$

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

The integrand has three simple poles inside the contour:
$\quad\ds{z_{m} \equiv \expo{2m\pi\ic/3}\,,\quad m = -1,0,1}$:
\begin{align}
&\color{#c00000}{\sum_{k = 0}^{n}{3n \choose 3k}}=
\sum_{m = -1}^{1}\lim_{z \to z_{m}}
\bracks{\pars{z - z_{m}}\,{z^{2}\pars{1 + z}^{3n} \over z^{3} - 1}}
=\sum_{m = -1}^{1}{z_{m}^{2}\pars{1 + z_{m}}^{3n} \over 3z_{m}^{2}}
\\[5mm]&={1 \over 3}\sum_{m = -1}^{1}\pars{1 + \expo{2m\pi\ic/3}}^{3n}
={1 \over 3}\sum_{m = -1}^{1}\expo{mn\pi\ic}
\pars{\expo{-m\pi\ic/3} + \expo{m\pi\ic/3}}^{3n}
\\[5mm]&={8^{n} \over 3}\sum_{m = -1}^{1}
\pars{-1}^{mn}\cos^{3n}\pars{m\,{\pi \over 3}}
\\[5mm]&={8^{n} \over 3}\bracks{\pars{-1}^{-n}\cos^{3n}\pars{-\,{\pi \over 3}}
+ 1 + \pars{-1}^{n}\cos^{3n}\pars{\pi \over 3}}
={8^{n} \over 3}\bracks{1 + 2\pars{-1}^{n}\pars{\half}^{3n}}
\\[5mm]&={8^{n} \over 3}\bracks{1 + {2\pars{-1}^{n} \over 8^{n}}}
\end{align}

$$
\color{#66f}{\large\sum_{k = 0}^{n}{3n \choose 3k}
={8^{n} + 2\pars{-1}^{n} \over 3}}
$$

A: I'll try to give a more detailed version of Gerry Myerson's hint.
If $S$ is your sum then you have
$$3S=(1+1)^{3n}+(1+e^{i\frac{2\pi}3})^{3n}+(1+e^{-i\frac{2\pi}3})^{3n}.$$
(To get this observe which terms get cancelled. If you are not familiar with this way of writing complex numbers, see Wikipedia.)
Now we want to simplify $(1+e^{i\frac{2\pi}3})^{3n}+(1+e^{-i\frac{2\pi}3})^{3n}$. We notice (by a direct computation - it helps if you draw a picture)
that $1+e^{i\frac{2\pi}3}=e^{i\frac\pi3}$ and $1+e^{i\frac{2\pi}3}=e^{-i\frac\pi3}$.
$$(1+e^{i\frac{2\pi}3})^{3n}+(1+e^{-i\frac{2\pi}3})^{3n} = (e^{i\frac\pi3})^{3n}+(e^{-i\frac\pi3})^{3n}=e^{in\pi}+e^{-in\pi}=(e^{i\pi})^n+(e^{-i\pi})^n.$$
Since $e^{i\pi}=e^{-i\pi}=-1$, you get
$$3S=2^{3n}+2(-1)^n=8^n+2(-1)^n.$$
The trick is very similar to the using $(1+1)^n+(1-1)^n$ to get the sum of even binomial coefficients, see this question: Evaluate $ \binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots+\binom{n}{2k}+\cdots$
A: $$f(x)=\sum_0^{3n}{3n\choose r}x^r=(1+x)^{3n}$$ Now let $a,b$ be the nonreal third roots of 1, and evaluate $$f(1)+f(a)+f(b)$$
