# Sum of every $k$th binomial coefficient.

It is widely known that $$\sum_{m=0}^{n} {n\choose m} = 2^n$$ and that $$\sum_{m=0}^{\lfloor\frac{n}{2}\rfloor}{n\choose 2m} = 2^{n-1}$$ Both results can be proven by exploting the nature of the roots of unity. Analagously, we can find $$\sum_{m=0}^{\lfloor\frac{n}{3}\rfloor}{n\choose 3m}$$ by taking the sum of the equations $$(1+1)^n = {n\choose 0} + {n\choose 1} + {n\choose 2} + {n\choose 3} + \cdots$$ $$(1+\omega)^n = {n\choose 0} + {n\choose 1}\omega + {n\choose 2}\omega^2 + {n\choose 3} + \cdots$$ $$(1+\omega^2)^n = {n\choose 0} + {n\choose 1}\omega^2 + {n\choose 2}\omega + {n\choose 3} + \cdots$$ by taking $\omega$ as a primitive cube root of $1$ and exploiting the fact that the roots of unity sum to $0$, i.e. $1 + \omega + \omega^2 = 0$.

The above method however seems to depend on the fact that every non-trivial root is primitive, so that the method only works for primes (For example, attemtping this method for $k=4$ will quickly run into problems as there is no longer full cancellation). Is there a generalization of this method for finding the sum of every $k$th binomial coefficient for arbitrary $k$? Failing that, does anyone know of any general method for finding such a sum?

-
–  Zev Chonoles May 7 '12 at 16:05
Could you elaborate on where you see problems for non-prime $k$? –  joriki May 7 '12 at 16:06
It works for all $k$. See en.wikipedia.org/wiki/Discrete_Fourier_transform . –  Qiaochu Yuan May 7 '12 at 16:20
By summing those equations, you would get $(1 + 1)^n + (1+\omega)^n + (1+\omega^2)^n =$ the sum of every third coefficient. But how do you get the closed form on that sum? –  andreas.vitikan Mar 14 '13 at 5:21

Actually the above method works for all numbers, not only primes. In your case for $n=4$, at the squares you get $1+(-1)+1+(-1)$.

Lemma Let $\omega_1,..,\omega_l$ be all l-th root of unity. Then

$$\sum_{i=1}^l \omega_i^k = \left\{ \begin{array}{l c} 0 & \mbox{ if l doesn't divide k} \\ l & \mbox{ if l divides k} \\ \end{array} \right.$$

Proof: Second is trivial. For First, pick some $\omega$ primitive root and observe that

$$\sum_{i=1}^l \omega_i^k = \sum_{i=1}^l \omega_i^k \omega^k$$

Thus

$$(1-\omega^k)\sum_{i=1}^l \omega_i^k =0$$

P.S. The same method can also be used to calculate $$\sum_{m=0}^{\lfloor\frac{n}{k}\rfloor}{n\choose km+r}$$ for $0 \leq r < k$. To do this, you simply add

$$\omega_i^{-r} (1+\omega_i)^n$$

-
In your first $\sum$ formula, I think you mean $m$, not $n$. It would probably be clearer if you hadn't made $m$ the multiplier, when the OP had $m$ as the bound variable of his $\sum$ –  Thomas Andrews May 7 '12 at 17:13
@ThomasAndrews Ty, fixed it... I think... –  N. S. May 7 '12 at 17:28