<s>[INST] Proving $\lim_{n\to\infty}\frac1n\sum_{i=0}^{n-1}\sum_{j=n}^{n+i}\frac{\binom{n+i}j}{2^{n+i}}=0$ I found the following question online: How can I prove that
$$\lim_{n\to\infty}\frac1n\sum_{i=0}^{n-1}\sum_{j=n}^{n+i}\frac{\binom{n+i}j}{2^{n+i}}=0$$
?
One notices that the inner sum is equal to the probability $\mathsf P\left(\mathrm B\left(n+i;\frac12\right)\geq n\right)$, where $\mathrm B$ denotes the binomial distribution. Using Hoeffding's inequality, one gets $\mathsf P\left(\mathrm B\left(n+i;\frac12\right)\geq n\right)\le\exp\left(-\frac{(n-i)^2}{2(n+i)}\right)$, i.e.
$$\tag1\label1\frac1n\sum_{i=0}^{n-1}\sum_{j=n}^{n+i}\frac{\binom{n+i}j}{2^{n+i}}\le\frac1n\sum_{i=0}^{n-1} \exp\left(-\frac{(n-i)^2}{2(n+i)}\right).$$
Based on numerical experiments, the right-hand side converges to $0$. If you apply $\exp(-x)\le\frac{1}{1+x}$, you get $$\tag2\label2\frac1n\sum_{i=0}^{n-1} \exp\left(-\frac{(n-i)^2}{2(n+i)}\right)\le\frac1n\sum_{i=0}^{n-1} \frac{1}{1+\frac{(n-i)^2}{2(n+i)}},$$
and the right-hand side still seems to converge to $0$. However, it is 2am so I lack the stamina to find a proof for this. I am asking for a sketch of proof that either the right-hand side in \eqref{1}, or even better, the right-hand side in \eqref{2} converges to $0$.
Note: Here, I answered a similar question.
 [/INST] We have
\begin{align}
\frac{1}{n}\sum_{i=0}^{n-1} \frac{1}{1 + \frac{(n-i)^2}{2(n+i)}}
&= \frac{1}{n}\sum_{i=0}^{n-\lfloor \sqrt{n} \rfloor} \frac{1}{1 + \frac{(n-i)^2}{2(n+i)}}
+ \frac{1}{n}\sum_{i=n+1-\lfloor \sqrt{n} \rfloor}^{n-1} \frac{1}{1 + \frac{(n-i)^2}{2(n+i)}}\\
&\le \frac{1}{n}\sum_{i=0}^{n-\lfloor \sqrt{n} \rfloor} \frac{1}{0 + \frac{(n-i)^2}{2(n+n)}}
+ \frac{1}{n}\sum_{i=n+1-\lfloor \sqrt{n} \rfloor}^{n-1} \frac{1}{1 + 0}\\
&= 4 \sum_{i=0}^{n-\lfloor \sqrt{n} \rfloor}\frac{1}{(n-i)^2} + \frac{\lfloor \sqrt{n} \rfloor - 1}{n}\\
&= 4 \sum_{m=\lfloor \sqrt{n} \rfloor}^n \frac{1}{m^2} + \frac{\lfloor \sqrt{n} \rfloor - 1}{n}.
\end{align}
From $\sum_{m=1}^\infty \frac{1}{m^2} = \frac{\pi^2}{6}$,
we know that $\lim_{n\to \infty} 4 \sum_{m=\lfloor \sqrt{n} \rfloor}^n \frac{1}{m^2} = 0$.
Also, clearly, $\lim_{n\to \infty} \frac{\lfloor \sqrt{n} \rfloor - 1}{n} = 0$.
The desired result follows. (Q. E. D.)
</s>