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?

  • 3
    See here: http://math.stackexchange.com/questions/128490/lacunary-sum-of-binomial-coefficients2012-05-07
  • 2
    Could you elaborate on where you see problems for non-prime $k$?2012-05-07
  • 2
    It works for all $k$. See http://en.wikipedia.org/wiki/Discrete_Fourier_transform .2012-05-07
  • 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
    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$2012-05-07
  • 0
    @ThomasAndrews Ty, fixed it... I think...2012-05-07