# Approximating binomial coefficient sum

I have the following exact sum for the expectation of an event

$$\sum_{m=0}^{nk} \sum_{j=1}^n (-1)^{j-1}\binom{n}{j} \binom{(n-j)k}{m} / \binom{nk}{m}$$

which is exactly correct but I want to give an upper bounding approximation that is easier to interpret. In particular, I want to see the expectations dependence on the parameter $$k$$. In simulation, it appears that as $$k \rightarrow \infty$$ we have that the sum tends towards $$n \log n$$. However, I am unsure how to show such a result analytically. My attempt has been to use some form of a stirling approximation on the binomial coefficients like $$\binom{n}{k} \leq \frac{n^k}{k!}$$ which can reduce the summation in the following way $$\sum_{m=0}^{nk} \sum_{j=1}^n (-1)^{j-1}\binom{n}{j} \frac{((n-j)k)^m}{m!} \cdot \frac{m!}{(nk)^m} = \sum_{m=0}^{nk} \sum_{j=1}^n (-1)^{j-1}\binom{n}{j} \left(1-\frac{j}{n}\right)^m$$ and from here maybe we can upper bound the $$(1-j/n)^m$$ to simplify further to a sum which depends only on $$j$$? Again comparing to simulation, it seems that when $$k \ll \log n$$ the sum will be something like $$nk$$ and for $$k \gg \log n$$ we will have the $$n \log n$$ (thus removing the dependence on $$k$$) but I can't seem to derive such a result.

Any help or advice would be greatly appreciated!

• In alternating sums, one-sided bounds like that do not work Dec 8, 2021 at 17:03
• Your post appears to contain at least two questions, depending on how $k$ and $\ln n$ compare to each other. It is better to have just one, quite specific, question per post. For one thing, this could make it more attractive to potential answerers. Dec 8, 2021 at 17:08
• @FedorPetrov this makes sense yes, is there any reasonable way of approximating this alternating sum then? Dec 8, 2021 at 17:13

Actually we may simply compute this sum (and I guess that your expectation may be computed differently to give the answer in the below simplified form). We start with $$1/{nk\choose m}=(nk+1)\int_0^1 x^m(1-x)^{nk-m}dx$$ by the Beta function $$B(a,b)=\Gamma(a)\Gamma(b)/\Gamma(a+b)$$ formula. Next, we sum up over $$m$$ with fixed $$j$$ to get $$\sum_{m=0}^{nk}\frac{(n-j)k\choose m}{nk\choose m}=(nk+1)\int_0^1 (1-x)^{jk}\sum{(n-j)k\choose m}x^m(1-x)^{(n-j)k-m}dx\\=(nk+1)\int_0^1(1-x)^{jk}\left(x+(1-x)\right)^{(n-j)k}dx=(nk+1)\int_0^1(1-x)^{jk}dx= (nk+1)\int_0^1 t^{jk}dt.$$ Then sum up over $$j$$ to get $$\sum_{m=0}^{nk} \sum_{j=1}^n (-1)^{j-1}\binom{n}{j} \binom{(n-j)k}{m} / \binom{nk}{m}=(nk+1)\int_0^1\sum_{j=1}^n(-1)^{j-1}{n\choose j}(t^k)^jdt\\=(nk+1)\int_0^1(1-(1-t^k)^n)dt=(nk+1)\left(1-\frac1k\int_0^1(1-s)^ns^{1/k-1}ds\right)\\=(nk+1)\left(1-\frac{\Gamma(n+1)\Gamma(1/k)}{k\Gamma(n+1/k+1)}\right)=(nk+1)\left(1-\frac{1\cdot 2 \cdot 3\cdot \ldots n}{(1+1/k)(2+1/k)\ldots (n+1/k)}\right).$$ Now your observation follows, for example, from $$\frac{\ell}{\ell+1/k}=\left(\frac{\ell}{\ell+1}\right)^{1/k}\cdot e^{O(1/(\ell^2 k))},$$ thus multiplying against $$\ell=1,\ldots,n$$ we get $$\frac{1\cdot 2 \cdot 3\cdot \ldots n}{(1+1/k)(2+1/k)\ldots (n+1/k)}=\frac{e^{O(1/k)}}{(n+1)^{1/k}}=\exp\left(-\frac{\log n+O(1)}k\right),$$ therefore in the $$\log n=o(k)$$ regime using $$1-\exp(-t)\sim t$$ for small $$t=\frac{\log n+O(1)}k$$ we indeed get $$n\log n$$ asymptotics for your sum.
• $t=1-x$ (change of variables in the integral). Dec 8, 2021 at 22:21