Exercise 1932Algebra › Complex numbersOlympiadAdded 4 Nov 2026

Binomial coefficients in steps of three

#roots of unity filter#binomial coefficients#complex numbers

Statement

Let $S_n=\binom n0+\binom n3+\binom n6+\cdots=\sum_{k\equiv0\ (3)}\binom nk$ .

Show that $S_n=\dfrac{2^n+2\cos\frac{n\pi}3}3$ .
Compute $S_{2024}$ .

Hint

Let $\omega=e^{2\pi i/3}$ . For an integer $k$ , $1+\omega^k+\omega^{2k}$ equals $3$ if $3\mid k$ and $0$ otherwise. Expand $(1+1)^n+(1+\omega)^n+(1+\omega^2)^n$ .

Show solutionHide solution

Solution

Filter. Using the hint,
$\sum_{j=0}^2(1+\omega^j)^n=\sum_{k=0}^n\binom nk\sum_{j=0}^2\omega^{jk}=3\sum_{3\mid k}\binom nk=3S_n.$

Evaluating. $1+\omega=-\omega^2=e^{i\pi/3}$ and $1+\omega^2=e^{-i\pi/3}$ . Hence
$3S_n=2^n+e^{in\pi/3}+e^{-in\pi/3}=2^n+2\cos\frac{n\pi}3.$

2. $2024=6\cdot337+2$ , so $\cos\frac{2024\pi}3=\cos\frac{2\pi}3=-\frac12$ and
$S_{2024}=\frac{2^{2024}-1}3.$

Check. $n=6$ : $\binom60+\binom63+\binom66=1+20+1=22$ , and the formula gives $\frac{64+2}3=22$ ✓.

Lesson. The roots of unity filter $\frac1m\sum_{j=0}^{m-1}\omega^{jk}=[m\mid k]$ extracts the terms whose index lies in a given residue class.

Binomial coefficients in steps of three

Statement

Solution

More problems in Complex numbers