7
$\begingroup$

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}$$

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

2 Answers 2

7
$\begingroup$

@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} $$

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

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$.

$\endgroup$
4
  • $\begingroup$ (+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! $\endgroup$
    – D S
    Feb 26 at 12:35
  • 1
    $\begingroup$ @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.) $\endgroup$ Feb 26 at 12:50
  • $\begingroup$ So the inequality is reversed when it is decreasing? $\endgroup$
    – D S
    Feb 26 at 12:52
  • $\begingroup$ @DS, Indeed, yes. :) $\endgroup$ Feb 26 at 13:02

You must log in to answer this question.

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