Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
See here: math.stackexchange.com/questions/128490/… –  Zev Chonoles May 7 '12 at 16:05
2  
Could you elaborate on where you see problems for non-prime $k$? –  joriki May 7 '12 at 16:06
2  
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

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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