Reorganising alternating sum of products of binomial coefficients

Question

The summation $$ \sum_{k=0}^{\lfloor\frac{p}{s}\rfloor}(-1)^k {n\choose k}{p-ks+n-1\choose n-1}\quad;n > 0, s > 0 \text{ and } 0\le p\le ns, $$ with ${n\choose k}$ denoting the binomial coefficient, has the limitation that implemented fixed sized integers, there are cases where individual terms exceed the integer size even though the result does not. (Even assuming ideal calculation of binomial coefficients.) Is there a way to reorganise that summation to avoid that? The integer size bound can be assumed to be $s^n$, the sum of that result for all $p$. A stronger result would that all terms summed do not exceed their sum in absolute value. A yet stronger result would be that all terms summed are non-negative. But even the weakest case is fine.

Answer 1

I cannot answer your question exactly, but assuming you are trying to compute this sum while avoiding integer overflow, here is a trick which might work. Let $a_k$ be the absolute value of the $k^{th}$ summand in your sum. You can prove that the numbers $a_k$ increase up to a point, and then decrease afterwards. This implies that your alternating sum is bounded above by the largest $a_k$. Letting $m=\max_k a_k$, you can compute $m$ in advance, and then you instead compute the sum with all additions performed modulo $m$. This ensures you never have any partial computations larger than $m$, while still giving the correct answer.

Answer 2

If the summation index $k$ went up to $n$ instead of $p/s \le n$, it would be the inclusion-exclusion formula for the number of $(n-1)$-subsets of $\{1,\dots,p+n-1\}$ that contain at least one element from each of the following $n$ disjoint intervals: $$ \{1,\dots,s\} \\ \{s+1,\dots,2s\} \\ \vdots \\ \{(n-1)s+1,\dots,ns\} $$ The number of such subsets is clearly $0$ because $n > n-1$. As in the linked answer, you can generalize by replacing the $n-1$ with any number smaller than $n$ and still obtain the same $0$ result.

So your sum is $$ \sum_{k=0}^{\lfloor p/s \rfloor}(-1)^k \binom{n}{k}\binom{p-ks+n-1}{n-1} = -\sum_{k=\lfloor p/s \rfloor+1}^n(-1)^k \binom{n}{k}\binom{p-ks+n-1}{n-1} $$

Answer 3

If you know that the final answer fits into the fixed integer size, then you don't have to worry about intermediate overflow. Computation with, say, $64$-bit integers is equivalent to computation modulo $2^{64}$. So even if intermediate answers overflow and give you something that's only correct modulo $2^{64}$ it still guarantees that the final answer is correct modulo $2^{64}$, which will be actually correct.

So for instance in $8$-bit integer arithmetic I can compute $$100 + 200 - 50 - 150$$ and get $100$, even though the partial sums don't fit into $8$ bits:

• With unsigned $8$-bit integers, $100+200$ would come to $44$, subtracting $50$ would yield $250$, and subtracting $150$ would yield $100$.
• With signed $8$-bit integers, the individual terms wouldn't even fit, and we'd be computing $100 + (-56) - 50 - (-106)$. The partial sums would be $100 + (-56) = 44$, $44-50 = -6$, and $-6 - (-106) = 100$.