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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.