For some fixed $0<p<1$, let $np\leq c<n$ and $2np\leq x< 2n$. Are there references or previous results for determining the asymptotics (as $n\to\infty$) of the partial sum $$ \sum_{k=x-c}^c\binom{n}{k}\binom{n}{x-k} $$ or equivalently if $c=n\lambda_1$ and $x=2n\lambda_2$, for constants $p\leq\lambda_2\leq\lambda_1<1$ $$ \sum_{k=2n\lambda_2-n\lambda_1}^{n\lambda_1}\binom{n}{k}\binom{n}{2n\lambda_2-k} $$

I don't think I can just apply Stirling's approximations to the binomial coefficients individual and take the sum and product.


Could someone comment if this is a valid attempt?

Using @robjohn's solution in this post, let $$ a_k=\binom{n}{k}\binom{n}{2n\lambda_2-k} $$ Then letting $k=n\lambda_2+j$, $$ \log\left(\frac{a_{k+1}}{a_k}\right)=-\frac{2j}{n\lambda_2(1-\lambda_2)}+O(n^{-1}) $$ Thus, $$ a_k=a_{n\lambda_2}\exp\left(-\frac{2j^2}{n\lambda_2(1-\lambda_2)}+O(j/n)\right) $$ Estimating $$ a_{n\lambda_2}\sim C(\lambda_2)=\frac{1}{2\pi n\lambda_2(1-\lambda_2)}(1-\lambda_2)^{-2n}\left(\frac{1-\lambda_2}{\lambda_2}\right)^{2n\lambda_2} $$ by Stirling's formula and using Riemann integral for the exponential, $$ \sum_{j=-n(\lambda_1-\lambda_2)}^{n(\lambda_1-\lambda_2)}\exp\left(-\frac{2j^2}{n\lambda_2(1-\lambda_2)}+O(j/n)\right)=\sqrt{n\lambda_2(1-\lambda_2)}\int_{-\infty}^{\infty}\exp\left(-2t^2\right)dt(1+O(1/n)) $$ we have \begin{eqnarray} \sum_{k=2n\lambda_2-n\lambda_1}^{n\lambda_1}\binom{n}{k}\binom{n}{2n\lambda_2-k}&\sim& C(\lambda_2)\sqrt{n\lambda_2(1-\lambda_2)}\sqrt{\pi/2}\\ &=&\frac{1}{2\sqrt{2\pi n\lambda_2(1-\lambda_2)}}(1-\lambda_2)^{-2n}\left(\frac{1-\lambda_2}{\lambda_2}\right)^{2n\lambda_2} \end{eqnarray} Substituting back $c=n\lambda_1$ and $x=2n\lambda_2$, and noticing Stirling's formula for $\binom{2n}{x}$, we get $$ \sum_{k=x-c}^c\binom{n}{k}\binom{n}{x-k}\sim\frac{1}{\sqrt{2}}\sqrt{\frac{2n}{2\pi x(2n-x)}}\left(\frac{2n}{2n-x}\right)^{2n}\left(\frac{2n-x}{x}\right)^x\sim \frac{1}{\sqrt{2}}\binom{2n}{x} $$ To me this is very interesting that it doesn't involve $c$, which disappeared when estimating with the Riemann integral above. However, after plugging in a couple of values in Mathematica, the approximation on the right hand side doesn't always give an accurate approximation to the partial sum.

QUESTION 2 Is there a way to figure out how far this partial sum is from the upper bound of $\binom{2n}{x}$?


It turns out that $$ \sum_{k=x-c}^c\binom{n}{k}\binom{n}{x-k}=\binom{2n}{x}-2\sum_{k=0}^{x-c-1}\binom{n}{k}\binom{n}{x-k} $$

I guess, then I'm interested in showing if $$ 2\sum_{k=0}^{x-c-1}\binom{n}{k}\binom{n}{x-k}=o\left(\binom{2n}{x}\right) $$ How would I go about showing this?


1 Answer 1


(Too long for comment): You can probably use the following asymptotic:

If $k \sim cn$ for a constant $c$ then $\dbinom{n}k = 2^{n(H(c)+o(1))}$ where $H(c)$ is the entropy function $H(c) = -c\log(c)-(1-c)\log(1-c)$. I think the key here is identifying which of these terms are the smallest and the largest and that should give you a hopefully good bound.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .