# 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?

-
math.stackexchange.com/q/918/152 –  Grigory M Oct 14 '12 at 12:50

$$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)$$

-

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*}

-
If $S$ is your sum then you have $$3S=2^{3n}=(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$