2
$\begingroup$

How can be calculate this following summation efficiently (is there some shorter formula for it) ?

$$\sum_{x=0}^{\frac{n}{k}}{n\choose k\cdot x}$$

$\endgroup$
0
$\begingroup$

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

Here is the answer $\sum_{i=0}^{\lfloor\frac{n}{k}\rfloor}{n \choose i * k}$ in a closed form

$\endgroup$
  • $\begingroup$ thank you for your answer. But how can efficiently compute this sum, we need to deal with complex numbers, which may lead to precision issues. Also, complexity will be n*k, which is very slow i guess. $\endgroup$ – caretaker Aug 25 '16 at 10:51
0
$\begingroup$

$$\sum_{k=0}^{\frac{n}{x}}\binom{n}{x\cdot k} = \binom{n}{x\cdot 1}+\binom{n}{x\cdot 2}+\binom{n}{x\cdot 3}+...+\underbrace{\binom{n}{x\cdot \frac{n}{x}}}_{\binom{n}{n}}$$

$\forall y \in \mathbb{N} : y = \frac{n}{x}$ $$\sum_{k=0}^{n}\binom{n}{x\cdot k} = \binom{n}{x\cdot 1}+\binom{n}{x\cdot 2}+\binom{n}{x\cdot 3}+\underbrace{\binom{n}{x\cdot y}}_{\binom{n}{n}}+\underbrace{\binom{n}{x\cdot (y+1)}+...+\binom{n}{x\cdot n}}_{0}$$

$$\sum_{k=0}^{\frac{n}{x}}\binom{n}{x\cdot k} =\sum_{k=0}^{n}\binom{n}{x\cdot k} $$

$\endgroup$

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.