<s>[INST] Evaluate $\sum_{k=0}^{n} {3n \choose 3k}$ Evaluate $\sum_{k=0}^{n} {3n \choose 3k}$.
It's not hard to evaluate by putting roots of unity. 
Therefore, I would like to see some solutions using elementary mathematical stuffs but not roots of unity. 
And the answer is $\frac{1}{3}(2^{3n}+2(-1)^n)$
 [/INST] If you let $f(n)$ be the sum in question, then, knowing the answer, we see that $$f(n+1)=7f(n)+8f(n-1).$$
If you can prove this recursion directly from the definition of $f(n)$ then you are done.
Now, by Vandermond's identity, we have: $$\begin{align}\binom{3n+3}{3k}=&\binom{3n-3}{3k-6}+6\binom{3n-3}{3k-5}+15\binom{3n-3}{3k-4}+20\binom{3n-3}{3k-3}\\
&+15\binom{3n-3}{3k-2}+6\binom{3n-3}{3k-1}+\binom{3n-3}{3k}
\end{align}\tag{1}$$
And:
$$\binom{3n}{3k}=\binom{3n-3}{3k-3}+3\binom{3n-3}{3k-2}+3\binom{3n-3}{3k-1}+\binom{3n-3}{3k}$$
This means that:
$$f(n)=\sum_{k=0}^{n-1} 2\binom{3n-3}{3k} + 3\sum_{k=1}^{n-1}\left(\binom{3n-3}{3k-2}+\binom{3n-3}{3k-1}\right)$$
So $$7f(n)+8f(n-1)=\sum_{k=0}^{n-1}22\binom{3n-3}{3k} + 21\sum_{k=1}^{n-1}\left(\binom{3n-3}{3k-2}+\binom{3n-3}{3k-1}\right)$$
Combine the terms of $(1)$ to get the same expression. 
To complete the induction, show that the expression is true for $n=0,1$.
</s>