While solving a programming problem, I stumbled across this sum.

$\sum_{i=0}^{\lfloor\frac{n}{k}\rfloor}{n \choose i * k}$

I know this can be solved by taking the $k^{th}$ root of unity and then summing them up so that only the multiples of $k$ remains. But what I can not figure out is how to proceed further and get a closed formula so that I can code it.

Thanks in advance.


Let $\omega$ be a primitive $k$th root of unity, so that for any integer $b$,

$$\frac1k\sum_{j=1}^k \omega^{bj} = \begin{cases}1,&k\mid b, \\ 0,&k\nmid b\end{cases}.$$

This allows us to write $\sum_{i=0}^{\lfloor\frac{n}{k}\rfloor}{n \choose i * k}$ as $$ \sum_{\substack{0\le b\le n,\\b \equiv 0 \pmod k}}{n \choose b} = \sum_{b=0}^n {n \choose b} \frac1k\sum_{j=1}^k \omega^{bj} = \frac1k \sum_{j=1}^k \sum_{b=0}^n {n\choose b} \omega^{bj}.$$

The innermost sum can be recognized as just the binomial expansion for $(1+\omega^j)^n$. So that means the desired sum is simply

$$\frac1k \sum_{j=1}^k (1+\omega^j)^n.$$

Now if you're coding this you might want to put some thought into what number system to evaluate $\omega$ in. You could do it using floating-point complex arithmetic but if $n$ is large you'll get a lot of precision loss in evaluating $(1+\omega^j)^n$ (but at least the end result can be rounded to an integer, albeit one with many digits). You could alternatively evaluate over different finite fields (say $\mathbb F_p$ where $p \equiv 1 \pmod k$ so that admits $k$th roots of unity), and then Chinese remainder the moduli together.

  • $\begingroup$ Can you please elaborate on " alternatively evaluate over different finite fields" and the field you mentioned or provide a link where I can read up more about this topic? Thank you. @ErickWong $\endgroup$ – smashingpumpkin Aug 25 '16 at 9:53
  • $\begingroup$ @smashingpumpkin The value you're looking for is an integer, so one could in principle ask 'what is the value mod $p$?" for a given prime $p$ For certain primes $p$ it is possible to interpret $\omega$ as an integer instead of a complex number. Then you can easily calculate the expression mod $p$. Do this for enough different $p$ and you can extract the original value by combining the results (you need an upper bound on the size of the number). $\endgroup$ – Erick Wong Aug 25 '16 at 14:59
  • $\begingroup$ A hybrid approach would be to use complex-valued arithmetic to get an approximation, determine an error interval for the estimate, then you only need enough primes to cover the length of the interval. $\endgroup$ – Erick Wong Aug 25 '16 at 16:24

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.