Question

Prove for all positive integers \(n\) :
\[
\sum_{k=0}^n\left(\begin{array}{l}
3 n \\
3 k
\end{array}\right)=\frac{1}{3}\left(2^{3 n}+2 \cdot(-1)^n\right)
\]

Answer 1

Let \(\zeta_{1,2}=\frac{-1 \pm i \sqrt{3}}{2}\) be the third roots of unity, i.e., \(\zeta_1^3=\zeta_2^3=1\). Then we have \(\zeta_1+\zeta_2+1=0, \zeta_1^2=\zeta_2\) and \(\zeta_2^2=\zeta_1\). If we plug \(y=1\) and \(x=1, x=\zeta_1, x=\zeta_2\) into the binomial theorem and add the equations, we obtain
\[
\sum_{l=0}^{3 n}\left(\begin{array}{c}
3 n \\
l
\end{array}\right)\left(1+\zeta_1^l+\zeta_2^l\right)=2^{3 n}+\left(1+\zeta_1\right)^{3 n}+\left(1+\zeta_2\right)^{3 n} .
\]
The expression \(1+\zeta_1^l+\zeta_2^l\) takes on different values depending on \(l\) : for \(l=3 k\), one has
\[
1+\zeta_1^l+\zeta_2^l=1+1^k+1^k=3,
\]
for \(l=3 k+1\),
\[
1+\zeta_1^l+\zeta_2^l=1+1^k \zeta_1+1^k \zeta_2=1+\zeta_1+\zeta_2=0
\]

and for \(l=3 k+2\),
\[
1+\zeta_1^l+\zeta_2^l=1+1^k \zeta_2+1^k \zeta_1=1+\zeta_2+\zeta_1=0
\]
hence
\[
\sum_{k=0}^n 3\left(\begin{array}{l}
3 n \\
3 k
\end{array}\right)=2^{3 n}+\left(1+\zeta_1\right)^{3 n}+\left(1+\zeta_2\right)^{3 n} .
\]
Now \(1+\zeta_{1,2}=\frac{1 \pm \sqrt{3} i}{2}\) are sixth roots of unity, i.e., \(\left(1+\zeta_{1,2}\right)^3=-1\) and \(\left(1+\zeta_{1,2}\right)^6=1\). Hence it follows immediately that
\[
\sum_{k=0}^n\left(\begin{array}{l}
3 n \\
3 k
\end{array}\right)=\frac{1}{3}\left(2^{3 n}+2 \cdot(-1)^n\right) .
\]