<s>[INST] 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?
 [/INST] 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*}$$
</s>