# Prove ${2n \choose n+i} \geq e^{-8 i^2/n} {2n \choose n}$

I am trying to prove $${2n \choose n+i} \geq e^{-8 i^2/n} {2n \choose n}$$ for $$0\leq i \leq n$$.

My attempt:

I rewrote $${2n \choose n+i}$$ to

$${2n \choose n+i} = {2n \choose n} \prod_{1\leq j \leq i} \left( 1- \frac{2j-1}{n+j} \right)$$

So all I need is to prove

$$\prod_{1\leq j \leq i} \left( 1- \frac{2j-1}{n+j} \right) \geq e^{-8i^2/n}$$

I tries using $$1-x \geq e^{-x/(1-x)}$$ inequality to get

$$\prod_{1\leq j \leq i} \left( 1- \frac{2j-1}{n+j} \right) \geq e^{- \sum_{j=1}^i \frac{2j-1}{n+1-j}}$$

However, I think this inequality is too loose. For example, for $$n=400$$ and $$i=399$$, it violates what we are trying to prove.

$$8 i^2/n < \sum_{j=1}^i \frac{2j-1}{n+1-j}$$

• @MartinR Yes, thank you just edited. Feb 25 at 12:18
• What is the source of the question?
– D S
Feb 25 at 12:44
• @DS Exercise 13.6.2 part E here courses.engr.illinois.edu/cs574/sp2024/lec/notes/lec/… Feb 25 at 14:09
• How did you prove part D?
– D S
Feb 25 at 14:16
• @DS Same method, but using the inequality $1-x \leq e^{-x}$ instead. The math goes through in this direction. Feb 25 at 14:20

@Sangchul Lee posted a stronger result already, but I just wanted to clarify that the argument I had in the question is salvageable to prove the weaker statement.

First, note that for $$i>n/2$$, the claim is trivially true. This is because $${2n \choose n}e^{-8i^2/n} \leq {2n \choose n}e^{-2n} \leq 2^{2n}e^{-2n} < 1 \leq {2n \choose n+i}$$

Hence, we can assume $$i\leq n/2$$. At which case $$(2i-1)/(n+i)<2/3$$ and the inequality $$1-x \geq e^{-3x}$$ holds for $$x<2/3$$. We have

$$\prod_{1\leq j \leq i} \left( 1- \frac{2j-1}{n+j} \right) \geq e^{-3 \sum_{j=1}^i \frac{2j-1}{n+j} } \geq e^{-\frac{3}{n}\sum_{j=1}^i (2j-1)} = e^{-3i^2/n} \geq e^{-8i^2/n}$$

• Do you mean $1-x\ge \exp(-3x)$?
– Gary
Feb 26 at 5:02
• @Gary Woops, yes! Fixed. Feb 26 at 5:03

Here is a stronger result:

Theorem. For $$0 \leq i \leq n$$, we have

$$\binom{2n}{n+i} \geq e^{-(\log 4)i^2/n} \binom{2n}{n}.$$

To begin with, we write

\begin{align*} \frac{\binom{2n}{n+i}}{\binom{2n}{n}} &= \frac{n!^2}{(n+i)!(n-i)!} \\ &= \frac{(k+n)!^2}{(k+n+i)!(k+n-i)!} \prod_{p=1}^{k} \left( 1 - \frac{i^2}{(n+p)^2} \right) \\ &= \prod_{p=1}^{\infty} \left( 1 - \frac{i^2}{(n+p)^2} \right) \end{align*}

where we let $$k \to \infty$$ in the last line and utilized the asymptotic formula $$\frac{(k+a)!}{k!} \sim k^a$$ as $$k \to \infty$$ (which itself can be easily proved using the Stirling's approximation). Now by noting that $$p \mapsto \log(1 - i^2/p^2)$$ is increasing for $$p > i$$, we get

\begin{align*} \log \frac{\binom{2n}{n+i}}{\binom{2n}{n}} &= \sum_{p=1}^{\infty} \log \left( 1 - \frac{i^2}{(n+p)^2} \right) \\ &\geq \int_{0}^{\infty} \log \left( 1 - \frac{i^2}{(n+p)^2} \right) \, \mathrm{d}p \\ &= i \int_{0}^{\frac{i}{n}} \frac{\log(1-x^2)}{x^2} \, \mathrm{d}x. \qquad \tag{x = \tfrac{i}{n+p}} \end{align*}

However, the function $$f(t) = \int_{0}^{t} \frac{\log(1-x^2)}{x^2} \, \mathrm{d}x$$ satisfies

\begin{align*} f(t) &= - \int_{0}^{t} \sum_{n=1}^{\infty} \frac{x^{2n-2}}{n} \, \mathrm{d}x = - \sum_{n=1}^{\infty} \frac{x^{2n-1}}{n(2n-1)}, \end{align*}

and in particular, $$f(0) = 0$$ and $$f''(t) \leq 0$$. Consequently, $$f$$ is concave and hence $$f(t) \geq f(1)t$$ for $$t \in [0, 1]$$. Moreover, the above power series expansion shows that $$f(1) = -2\log 2$$. Therefore

\begin{align*} \log \frac{\binom{2n}{n+i}}{\binom{2n}{n}} &\geq i f\left(\frac{i}{n}\right) \geq f(1) \frac{i^2}{n} = -(\log 4)\frac{i^2}{n} \end{align*}

for $$0 \leq i \leq n$$.

• (+1) though I am not much familiar with when we can use integrals for inequalities related to sums. I understood the whole answer, except the line $\geq \int_{0}^{\infty} \log \left( 1 - \frac{i^2}{(n+p)^2} \right) \, \mathrm{d}p$. Can you direct me to appropriate reading material? Thanks!
– D S
Feb 26 at 12:35
• @DS, No problem. If you have an increasing function $f : [0, \infty)\to\mathbb{R}$, then for each positive integer $k$ we have $$f(x)\leq f(k), \qquad k-1\leq x\leq k.$$ Integrating both sides w.r.t. $x$ on $[k-1, k]$ then tives $$\int_{k-1}^{k}f(x)\,\mathrm{d}x\leq f(k),$$ and summing this for $k=1,2,\ldots$ allows us to compare the sum $\sum_k f(k)$ with the corresponding integral. (This can be also visualized by recognizing the inequality as a comparison between areas, which is also how we derive the integral test for series.) Feb 26 at 12:50
• So the inequality is reversed when it is decreasing?
– D S
Feb 26 at 12:52
• @DS, Indeed, yes. :) Feb 26 at 13:02