2
$\begingroup$

This question already has an answer here:

What are common lower bounds for ${{2n} \choose {n}}$?


Edit: I made a mistake in my original question.

It doesn't change my question but there is no reason for me to include the mistake.

$\endgroup$

marked as duplicate by Jack D'Aurizio inequality Mar 20 '18 at 20:51

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ You could try stirling's approximation on $\frac{(2n)!}{n!^2}$ $\endgroup$ – vrugtehagel Mar 20 '18 at 19:34
  • $\begingroup$ Stirling's gives roughly $4^n$ I do not recall the details, but easy enough to do again: $\endgroup$ – Will Jagy Mar 20 '18 at 19:34
  • 1
    $\begingroup$ $2n/n=2$, not $n$. $\endgroup$ – John Brevik Mar 20 '18 at 19:34
  • 1
    $\begingroup$ Here is a tight lower bound for Catalan numbers, which are $\frac{1}{n+1} {2n \choose n}$. $\endgroup$ – mechanodroid Mar 20 '18 at 19:35
4
$\begingroup$

Using the bounds from this answer, we have $$ \frac{4^n}{\sqrt{\pi\left(n+\frac13\right)}}\le\binom{2n}{n}\le\frac{4^n}{\sqrt{\pi\left(n+\frac14\right)}} $$

$\endgroup$
  • $\begingroup$ good; from Stirling's, the squared denominator keeps an extra $\sqrt n$ compared with the denominator. I wasn't sure yet $\endgroup$ – Will Jagy Mar 20 '18 at 19:44
  • $\begingroup$ @robjohn is this a better estimator than Stirling's? $\endgroup$ – gimusi Mar 20 '18 at 20:01
  • 1
    $\begingroup$ @gimusi: you can easily notice that $\frac{1}{\sqrt{\pi}}>\frac{2\sqrt{\pi}}{e^2}$, hence robjohn's bound is sharper than yours. Also because the constant in robjohn's answer is optimal. $\endgroup$ – Jack D'Aurizio Mar 20 '18 at 20:07
  • $\begingroup$ @JackD'Aurizio oh yes of course! Indeed it is a very narrow bound. I will take a look to the derivation. Thanks $\endgroup$ – gimusi Mar 20 '18 at 20:09
  • 1
    $\begingroup$ @user: note that $\lim\limits_{n\to\infty}\left[\,\raise{4pt}{\frac{16^n}{\pi\binom{2n}{n}^2}}-n\,\right]=\frac14$, so the $\frac14$ in the upper bound is optimal. The $\frac13$ in the lower bound can be replaced by $\frac1\pi$ and the inequality will still be valid for $n\ge0$. $\endgroup$ – robjohn Mar 20 '18 at 21:29
4
$\begingroup$

Using Stirling's bound

$$\sqrt{2\pi}\ n^{n+\frac12}e^{-n} \le n! \le e\ n^{n+\frac12}e^{-n}$$

we obtain

$$\binom{2n}{n}=\frac{(2n)!}{n!^2}\ge\frac{\sqrt{2\pi}\ (2n)^{2n+\frac12}e^{-2n}}{e^2\ n^{2n+1}e^{-2n}}=\frac{\sqrt{2\pi}\ 2^{2n}2^{\frac12}n^{2n+\frac12}}{e^2\ n^{2n+1}}=\frac{2\sqrt{\pi}}{e^2}\frac{4^n}{\sqrt n}$$

$\endgroup$
0
$\begingroup$

Erdös had a really nice lower bound, which he used in his proof of Bertrand's Postulate: $4^n/2n \leqslant {{2n}\choose{n}}$. This follows because \begin{align*} (1+1)^{2n}=\sum_{k=0}^{2n} {{2n}\choose{k}} < 1+2n{{2n}\choose{n}} \end{align*} and then $4^n \leqslant 2n{{2n}\choose{n}}$. In fact the bound can be strengthened without too much difficulty to give $4^n/n \leqslant {{2n}\choose{n}}$.

Edit: The stronger bound only holds for $n \geqslant 4$.

$\endgroup$

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