There is an exercise question on my textbook: Suppose there is an n-element set, how many of its subsets have cardinality divisible by 3?
The hint on the textbook says "use the binomial formula with $x = \zeta$, where $ζ^3 = 1$".
What $\zeta$ is it referring to? Why is the binomial formula related to this question? (I'm totally confused because the chapter is about elementary counting and Stirling number and it does not talk anything about $\zeta$)
So, the number of subsets with cardinality a multiple of $3$ is $$S={n\choose 0}+{n\choose 3}+{n\choose 6}+\dots=\sum_{k\geq 0}{n\choose k}\delta(k\equiv 0 \mod 3).$$. Now, note that $$\delta(k\equiv 0 \mod 3)=\frac{1+\zeta^k+\zeta^{2k}}{3}$$ (Because $1+\zeta^k+\zeta^{2k}=3$ if $k\equiv 0\mod 3$ and $1+\zeta^k+\zeta^{2k}=\frac{\zeta^{3k}-1}{\zeta^k-1}=0$ if $k\not\equiv 0\mod 3$ )
Then, you have \begin{align*} S=&\sum_{k\geq 0}{n\choose k}\frac{1+\zeta^k+\zeta^{2k}}{3}\\ =&\frac{1}{3}\left(\sum_{k\geq 0}{n\choose k}1+ \sum_{k\geq 0}{n\choose k}\zeta^k+ \sum_{k\geq 0}{n\choose k}\zeta^{2k} \right)\\ =&\frac{1}{3}\left((1+1)^n+(1+\zeta)^n+(1+\zeta^2)^n\right) \end{align*} Edit: Thanks to @Mike comment below, note that $$(1+\zeta)^n+(1+\zeta^2)^n=2\Re\left((1+\zeta)^n\right)=2\Re\left((-\zeta^2)^n\right)=2\Re\left((-1)^n(e^{4n\pi i/3})\right)=2(-1)^n\cos(4n\pi/3)=2\cos(4n\pi/3-n\pi)=2\cos(n\pi/3)$$ So, at the end the answer will be $$\frac{1}{3}\left(2^n+2\cos(n\pi/3)\right)$$