Lower bounds for ${{2n} \choose {n}}$ [duplicate]

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.

marked as duplicate by Jack D'Aurizio inequality StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Mar 20 '18 at 20:51

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

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

• good; from Stirling's, the squared denominator keeps an extra $\sqrt n$ compared with the denominator. I wasn't sure yet – Will Jagy Mar 20 '18 at 19:44
• @robjohn is this a better estimator than Stirling's? – gimusi Mar 20 '18 at 20:01
• @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. – Jack D'Aurizio Mar 20 '18 at 20:07
• @JackD'Aurizio oh yes of course! Indeed it is a very narrow bound. I will take a look to the derivation. Thanks – gimusi Mar 20 '18 at 20:09
• @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$. – robjohn Mar 20 '18 at 21:29

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

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