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?


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)$.

This lemma will help you:

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$$


$$(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$$

  • $\begingroup$ 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$ $\endgroup$ May 7 '12 at 17:13
  • $\begingroup$ @ThomasAndrews Ty, fixed it... I think... $\endgroup$
    – N. S.
    May 7 '12 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.