Question

Is there a quick formula to find the ratios; $\displaystyle\frac{r(k)}{rtotal}$ for $k=1 \dots n$ without calculating the numerator and the denominator where;

$\displaystyle r(k) = \sum\limits_{i=1}^{n} {{n^2 \choose (k-1)*n+i}}$ and $\displaystyle rtotal = \sum\limits_{k=0}^{n} {r(k)}$.

I know the denominator $\displaystyle rtotal={n^2 \choose 0} + {n^2 \choose 1} + \dots + {n^2 \choose n^2} = 2^{n^2}$

If I can find a formula for each numerator;

$\displaystyle r(1)={n^2 \choose 1} + \dots + {n^2 \choose n} = ?$

$\displaystyle r(2)={n^2 \choose n+1} + \dots + {n^2 \choose 2n} = ?$

$\dots$

$\displaystyle r(n)={n^2 \choose (n-1)*n+1} + \dots + {n^2 \choose n^2} = ?$

then some cancelling would be possible yielding to easier calculations. I need the ratios for $1 < n < 100$ but for $n>40$, $rtotal$ gets huge in my program.

Answer 1

If you are interested in approximations to your ratios, you may find the accepted answer (and some comments of mine) to this MathOverflow post useful: http://mathoverflow.net/questions/17202/sum-of-the-first-k-binomial-coefficients-for-fixed-n .

Essentially, the approximations are geometric series starting with the dominant term in your sums, and except for k near n/2, should serve you well, especially if you collapse adjacent terms in the form of n^2 +1 choose j. For k near n/2, Michael Lugo has some suggestions in his answer to the question above. If you do a search on "binomial coefficients sum", you will find other MathOverflow posts considering sums similar to yours which might help you.

I think getting a nice closed form for the exact values for your numerators in general is unsolvable.

Gerhard "Ask Me About System Design" Paseman, 2011.10.28