<s>[INST] Combinations and Summations" $\sum_{x=0}^{n/k} \binom n{kx}$ 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}$$

 [/INST] $$\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} $$

</s>