# Calculating a sum which includes binomial coeffeicients

Some formula for calculating the probablity that the difference between the number $6$ and the average of accidentally selected $100$ points among $10000$ points which are distributed in the interval $[2,8]$ with equal distances, is not more than $0.05$; lead to this sum:

$$\sum_{r=493701}^{506199}\sum_{k=0}^{100}(-1)^k\frac{\binom{100}{k}\binom{r-10001k+99}{99}}{\binom{r+99}{r}}$$

It seems that if $r-10001k+99$ is negative then $\binom{r-10001k+99}{99}$ is to be considered zero. btw, it may not be important if there is a calculator or a way that can deal with the sum; then I will correct the details. I tried to calculate it in Wolframalpha with this command:

Sum[Sum[((-1)^k)*Binomial[100,k]*Binomial[r-10001*k+99,99]/Binomial[r+99,r],{k,1,100}],{r,493701,506199}]


But it didn't show me any result. Online Sage seems to be out of access for my internet connection. Is there any other way to calculate or estimate the result of these iterated sums?

Also I tested gap with:

sign:= function(n)
if n < 0 then
return 0;
elif n = 0 then
return 0;
else
return 1;
fi;
end;

Sum([493701..506199],r->Sum([0..100],k->((-1)^k)*Binomial(100,k)*Binomial(r-10001*k+99,99)*sign(r-10001*k+99)/Binomial(r+99,r)));


and the result:

<integer 714...349 (28661 digits)>/<integer 547...000 (28670 digits)>


Edit: Clément Guérin's answer suggests to write:

$$\sum_{r=493701}^{506199}\sum_{k=0}^{100}(-1)^k\frac{\binom{100}{k}\binom{r-10001k+99}{99}}{\binom{r+99}{r}} = \sum_{k=0}^{100}(-1)^k\binom{100}{k}\sum_{r=493701}^{506199}\frac{\binom{r-10001k+99}{99}}{\binom{r+99}{r}} = \sum_{k=0}^{100}(-1)^k\binom{100}{k}\sum_{r=493701}^{506199}\prod_{s=1}^{99}\left(1-\frac{10001k}{r+s} \right)$$ But I couldn't give this to Wolfram. In fact, one should calculate $$\sum_{k=0}^{100}(-1)^k\binom{100}{k}\sum_{r=493701}^{506199}\prod_{s=1}^{99}\left(1-\frac{10001k}{r+s} \right)\frac{sgn(r-10001k+99)+1}{2}.$$

• I am very curious to see the problem that led to this answer. Can you post the same here too? Also, wondering whether the limits of sum over the values of variable $r$ were supposed to be symmetric about the $500000$ value, in which case, the lower limit of the sum should be $493801$ instead of $493701$ – Deepak Gupta Sep 11 '15 at 6:51
• With "numerators" that big, I'd go with Sterling's approximation, to approximate. It's still a huge sum ... I'd also like to know where this came from. – Christopher Carl Heckman Sep 11 '15 at 6:57
• @DeepakGupta: No the limits are correct. The problem is about the probablity that the difference between 6 and the average of accidentally selected 100 points among 10000 points which are distributed in the interval $[2,8]$ with equal distances, is not more than 0.05. – user795571 Sep 11 '15 at 7:13
• @user795571: Then you can directly approximate the original problem by approximating the distribution of that sum by a Gaussian distribution. – joriki Sep 11 '15 at 7:22
• You may also try FUtil package by Frank Lübeck, see in particular this section in its manual. Note that this package is not redistributed with GAP so you have to install it yourself. – Alexander Konovalov Sep 13 '15 at 21:08

First (setting r'=r+99) :

$$\frac{\binom{r-10001k+99}{99}}{\binom{r+99}{r}}=\prod_{i=0}^{98}(1-\frac{10001k}{r'-i})$$

Hence :

$$\frac{\binom{r-10001k+99}{99}}{\binom{r+99}{r}}=1+\sum_{s=1}^{99}(-1)^s\sum_{0\leq i_1<...<i_s\leq 98}\frac{(10001k)^s}{(r'-i_1)...(r'-i_s)}$$

Now your sum is equal to :

$$\sum_{r=493701}^{506199}\sum_{k=0}^{100}(-1)^k\frac{\binom{100}{k}\binom{r-10001k+99}{99}}{\binom{r+99}{r}}=$$

$$\sum_{r=493701}^{506199}\sum_{k=0}^{100}(-1)^k\binom{100}{k}+\sum_{r=493701}^{506199}\sum_{s=1}^{99}(-1)^s\sum_{0\leq i_1<...<i_s\leq 98}\frac{10001^s}{(r'-i_1)...(r'-i_s)}\sum_{k=0}^{100}(-1)^k\binom{100}{k}k^s$$

Now I claim that for any $s<n$ we have that‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌:

$$\sum_{k=0}^n(-1)^k\begin{pmatrix}n\\k\end{pmatrix}k^s=0$$

I won't prove it generally, for $s=0$ this is the binomial formula.

For $s=1$ :

$$\sum_{k=0}^nkx^k\begin{pmatrix}n\\k\end{pmatrix}=x\times \frac{d}{dx}(x+1)^n=nx(x+1)^{n-1}$$

So this is true. For $s=2$ :

$$\sum_{k=0}^nk^2x^k\begin{pmatrix}n\\k\end{pmatrix}=x\times \frac{d}{dx}x\times \frac{d}{dx}(x+1)^n=x\frac{d}{dx}nx(x+1)^{n-1}=xn(x+1)^{n-1}+x^2n(n-1)(x+1)^{n-2}$$

And so on...

Finally this gives that the your probability is null(!). Although I cannot se where is the error, I might be wrong (given that you are looking for a probability), anyway I think there is a way here to help you compute the sum.

• I think the problem is that you're applying the conventional definition of binomial coefficients with negative upper index, whereas I suspect that in the question these coefficients are meant to be interpreted as zero. (You may have overlooked that the upper index becomes negative because you dropped one of the zeros in $10001$ in the right-hand sides.) – joriki Sep 11 '15 at 8:14
• I hope I can arrage your calculation and use wolfram again to see if it gives the results. – user795571 Sep 11 '15 at 8:37
• @joriki, thanks, that's why, I was wrong – Clément Guérin Sep 11 '15 at 11:41
• @user795571, sorry about my mistake, it worked with $1001$... – Clément Guérin Sep 11 '15 at 11:42