My teacher was discussing binomial expansions of $(1 + x)^n$ and he gave as an interesting example with $x = i$ whereby you could obtain the sum of all the odd coefficients ($C_n^1+ C_n^3+ C_n^5 …$) and the even ones. Then by appying deMoivre to $(1 + i)^n$ you could separate the binomial expansion into a real and an imaginary part and compute those separately.
How can I, in a somewhat similar manner, determine the sum of every kth binomial coefficient, using the kth unity root?
By substituting into $(1 + x)^n$ all of the unity roots on by one and then adding the results the results is the sum of every k-th coefficient is equal to $(1 + 1)^n + (1 + \omega)^n + (1 + \omega^2)^n$ but how can I get the closed form for this sum?
Best Answer
The keyword is discrete Fourier transform. The basic lemma is that if $\zeta_k$ is a primitive $k^{th}$ root of unity then
$$\sum_{i=0}^{k-1} \zeta_k^{ij} = \begin{cases} 0 \text{ if } k \nmid j \\ k \text{ otherwise}. \end{cases}$$
It follows that if $f(x) = \sum a_i x^i$ is a formal power series then the sum of every $k^{th}$ term of $f$ is
$$\sum a_{ki} x^{ki} = \frac{1}{k} \sum_{i=0}^{k-1} f(\zeta_k^i x).$$
In this particular case we have, for example,
$$\sum {n \choose 2i} = \frac{1}{2} \left( (1 + 1)^n + (1 - 1)^n \right) = 2^{n-1}$$
and
$$\sum {n \choose 3i} = \frac{1}{3} \left( (1 + 1)^n + (1 + \omega)^n + (1 + \omega^2)^n \right) = \frac{2^n + (-\omega^2)^n + (-\omega)^n}{3}$$
where $\omega$ is a primitive third root of unity (and we used the fact that $1 + \omega + \omega^2 = 0$). The answer is messier in general.