5
$\begingroup$

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?

  • 0
    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?2013-03-14

1 Answers 1

3

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$

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$

  • 0
    @ThomasAndrews Ty, fixed it... I think...2012-05-07