Binomial sum invoking roots of unity

Evalute (in a closed form) the sum:

$$\sum_{k=0}^{n}\binom{3n}{3k}$$

Solution



Let $\omega=e^{2\pi i /3}$ . The binomial expansion tells us

$$\left ( 1+x \right )^n = \sum_{k=0}^{n}\binom{n}{k}x^n$$

Subbing $x$ with $1, \omega, \omega^2$ respectively at the binomial expansion we get:

$$\begin{matrix}
\displaystyle \sum_{k=0}^{n}\binom{n}{k}=2^n & , &\displaystyle \left ( 1+\omega \right )^n =\sum_{k=0}^{n}\binom{n}{k}\omega^n &, &\displaystyle \left ( 1+\omega^2 \right )^n = \sum_{k=0}^{n} \binom{n}{k}\omega^{2k}
\end{matrix}$$

Adding the above three equations together we get that:

$$\sum_{k=0}^{n}\binom{n}{k}\left [ 1+\omega^k +\omega^{2k} \right ]=2^n + \left ( 1+\omega \right )^n + \left ( 1+\omega^2 \right )^n  $$

We note that $1+\omega^k +\omega^{2k}=3$ when $k$ is divisible by $3$ and $0$ othewise. Hence:

$$\sum_{m=0}^{\left \lfloor n/3 \right \rfloor}\binom{n}{3m}= \frac{1}{3}\left [ 2^n + \left ( 1+\omega \right )^n+ \left ( 1+\omega^2 \right )^n \right ]$$

Subbing $n$ with $3n$ and doing a bit of algebra (complex powers) we finally get that:

$$\sum_{k=0}^{n}\binom{3n}{3k}= \frac{1}{3}\left [ 8^n + 2(-1)^n \right ]$$

and the exercise comes to an end.

The exercise can also be found in mathematica.gr