For $n\in\Bbb N$, define $$S_n=\sum_{p=0}^n\sum_{q=0}^n\binom{n}{p}\binom{n}{q} e^{-pq}$$ I want to prove that $$\lim_{n\to\infty}\frac{S_n}{2^{n+1}}=1$$

My attempts:

  • For $n\in\Bbb N^*$, $$S_n=2^{n+1}-1+\sum_{p=1}^n\sum_{q=1}^n\binom{n}{p}\binom{n}{q} e^{-pq}$$

  • The role of $e$ is not important. In fact, we can replace $e$ with any constant $x\ge1$.

  • I tried to use some similar methods (such as CLT) of the limit below but failed. $$\lim_{n\to\infty} e^{-n} \sum_{k=0}^{n} \frac{n^k}{k!}=\frac12$$

  • Summation of $q$ gives $$S_n=\sum_{p=0}^n\binom{n}{p}(1+e^{-p})^{n}$$

  • Some calculation results: $$\frac{S_{10}}{2^{11}}\simeq1.23\qquad\frac{S_{20}}{2^{21}}\simeq1.01\qquad\frac{S_{30}}{2^{31}}\simeq1.00035$$

The answer of the link in my comment is satisfied. However, it will also be appreciated if there are any other ideas.


If both $p$ and $q$ are $\geq 2$ then $pq\geq p+q$ and this allows an elementary estimation. We have

$$ S_n = 2^{n+1}+2n\left(1+\frac{1}{e}\right)^n-\left(1+2n+\frac{n^2}{e}\right) +\sum_{p,q\in[2,n]}\binom{n}{p}\binom{n}{q}e^{-pq}$$ and $$\sum_{p,q\in[2,n]}\binom{n}{p}\binom{n}{q}e^{-pq}\leq \sum_{p,q\in[2,n]}\binom{n}{p}\binom{n}{q}e^{-(p+q)}=\left(\sum_{p=2}^{n}\binom{n}{p}e^{-p}\right)^2\leq\left(1+\frac{1}{e}\right)^{2n} $$ so the claim follows from the fact that $\left(1+\frac{1}{e}\right)^2<2$.

This is not really related to the current problem but I believe it is interesting, anyway.
The last inequality can be proved through Cauchy-Schwarz: for instance, $$ \int_{0}^{1}\left(1+\frac{x}{2}\right)^2\,dx\int_{0}^{1}e^x\,dx \geq \left(\int_{0}^{1}\left(1+\frac{x}{2}\right) e^{x/2}\,dx \right)^2 $$ leads to $\frac{19}{12}(e-1)\geq e$, hence to $\color{red}{e\geq\frac{19}{7}}$ and $$ \left(1+\frac{1}{e}\right)^2 \leq \left(\frac{26}{19}\right)^2<2. $$

| cite | improve this answer | |

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.