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

First, observe that
$$\sum\limits_{k=0}^n \binom{3n}{3k} = \sum\limits_{k=0}^n \binom{3n-3}{3k} + 3\binom{3n-3}{3k-1} + 3\binom{3n-3}{3k-2} + \binom{3n-3}{3k-3}$$
by repeated expansion using Pascal's recurrence. Also, due to the limits on $k$ and the fact that $\binom{n}{m} = 0$ whenever $m \leq 0$ or $m > n$, we can write this
$$\sum\limits_{k=0}^n \binom{3n}{3k} = 3\sum\limits_{k=0}^n \bigg{(} \binom{3n-3}{3k-1} + \binom{3n-3}{3k-2} \bigg{)} + 2\sum\limits_{k=0}^n \binom{3n-3}{3k-3}$$
Now, let $F_n = \sum\limits_{k=0}^n \binom{3n}{3k}$. We use this substitution and the fact that the given sum over two binomial coefficients spans all binomial coefficients except those with bottom part a multiple of 3 to obtain;
$$F_n = 3\bigg{(} 2^{3n-3} - F_{n-1} \bigg{)} + 2F_{n-1} \implies F_n + F_{n-1} = 3*2^{3n-3}$$
To solve a linear nonhomogeneous recurrence like this, we let $F_n = h_n + p_n$ where $h_n$ is the homogeneous solution and $p_n$ is a particular solution to the nonhomogeneous form.
Solving $h_n + h_{n-1} = 0$ yields $h_n = A*(-1)^n$. We assume $p_n$ is of the form $p_n = B*2^{3n}$ and we solve;
$$p_n + p_{n-1} = 3*2^{3n-3} \implies B2^{3n-3}(2^{3} + 1) = 3*2^{3n-3}$$
which simplifies to $B = \dfrac{1}{3}$, so that $p_n = \dfrac{1}{3} 2^{3n}$.
Using an initial value to solve for $A$ suffices to prove the same formula the author claims.
