12
$\begingroup$

What is the tightest upper bound we can establish on the central binomial coefficients $ 2n \choose n$ ?

I just tried to proceed a bit, like this:

$ n! > n^{\frac{n}{2}} $

for all $ n>2 $. Thus,

$ \binom{2n}{n} = \frac{ (n+1) \ldots (2n) }{n!} < \frac{\left(\frac{\sum_{k=1}^n (n+k) }{n}\right)^n }{n^{n/2}} = \frac{ \left( \frac{ n^2 + \frac{n(n+1)}{2} }{n} \right) ^n}{n^{n/2}} = \left( \frac{3n+1}{2\sqrt{n}} \right)^n $

But, I was searching for more tighter bounds using elementary mathematics only (not using Stirling's approximation etc.).

$\endgroup$
2
  • 2
    $\begingroup$ The simplest upper bound to prove is $4^n$ (which is still stronger than your bound) and just follows from the binomial expansion of $(1+1)^{2n}$. Peter's answer gives a less wasteful estimate. $\endgroup$ Jun 14 '13 at 13:00
  • $\begingroup$ I should have thought about it. Yes, Peter's bound is very good, I tested it too. $\endgroup$ Jun 14 '13 at 13:54
15
$\begingroup$

Here's a way to motivate and refine the argument that Péter Komjáth attributes to Erdős.

Start by computing the ratio between the $n$-th and $(n-1)$-st central binomial coefficients: $$ {2n \choose n} \left/ {2(n-1) \choose n-1} \right. = \frac{(2n)! \phantom. / \phantom. n!^2}{(2n-2)! \phantom. / \phantom. (n-1)^2} = \frac{(2n)(2n-1)}{n^2} = 4 \left( 1 - \frac1{2n} \right). $$ For large $n$, this ratio approaches $4$, suggesting that $2n \choose n$ grows roughly as $4^n$. If the factor $1 - \frac1{2n}$ were $1 - \frac1n = (n-1)/n$, the growth would be exactly proportional to $n^{-1} 4^n$. Since $1 - \frac1{2n}$ is (for large $n$) nearly the square root of $1 - \frac1n$, the actual asymptotic should be proportional to $n^{-1/2} 4^n$. So we introduce the ratio $$ r_n := \left( {2n \choose n} \left/ \frac{4^n}{\sqrt n} \right. \right)^2 = \frac{n}{16^n} {2n \choose n}^2. $$ Then $$ \frac{r_n}{r_{n-1}} = \left( 1 - \frac1{2n} \right)^2 \left/ \left( 1 - \frac1n \right) \right. = \frac{(2n-1)^2}{(2n-2)(2n)} \gt 1. $$ Thus $r_{n-1} < r_n$; and since $r_1 = (2/4)^2 = 1/4$ we have by induction $$ r_1 \lt r_2 \lt r_3 \lt r_4 \lt \cdots \lt r_n = \frac12 \frac{1 \cdot 3}{2 \cdot 2} \frac{3 \cdot 5}{4 \cdot 4} \frac{5 \cdot 7}{6 \cdot 6} \cdots \frac{(2n-3)(2n-1)}{(2n-2)(2n-2)} \frac{2n-1}{2n}. $$ Each $r_{n_0}$ gives a lower bound on $r_n$, and thus on $2n\choose n$, for all $n \geq n_0$. The OP asked for upper bounds, so consider $$ R_n := \frac{2n}{2n-1} r_n = \frac{n}{\left(1-\frac 1{2n}\right)16^n} {2n \choose n}^2. $$ Now $R_{n+1}/R_n = (2n-1)(2n+1) \phantom. / \phantom. (2n)^2 = (4n^2-1) \phantom. / \phantom. (4n^2) \lt 1$, so $$ \frac12 = R_1 \gt R_2 \gt R_3 \gt R_4 \gt \cdots \gt R_{n+1} = \frac12 \frac{1 \cdot 3}{2 \cdot 2} \frac{3 \cdot 5}{4 \cdot 4} \frac{5 \cdot 7}{6 \cdot 6} \cdots \frac{(2n-3)(2n-1)}{(2n-2)(2n-2)}. $$ It follows that $R_n \geq r_{n'}$ for any $n,n'$, so $R_1=1/2$, $R_2=3/8$, $R_3=45/128$, etc. are a series of upper bounds on every $r_n$. Since moreover $r_n / R_n = 1 - \frac1{2n} \rightarrow 1$ as $n \rightarrow \infty$, both $r_n$ and $R_n$ converge to a common limit that is an upper bound on every $r_n$. If we accept Wallis's product (which is classical though not as elementary as everything else in our analysis), then we can evaluate this common limit as $1/\pi$ and thus recover the asymptotically sharp upper bound ${2n \choose n} < 4^n / \sqrt{\pi n}$.

$\endgroup$
2
  • 2
    $\begingroup$ +1, and let me challenge your statement that the Wallis product is not as elementary, by pointing to the Monthly note math.chalmers.se/~wastlund/monthly.pdf and the 16th Christmas Tree Lecture by Don Knuth, "Why pi?" (now on youtube). $\endgroup$ Jul 1 '13 at 16:58
  • 4
    $\begingroup$ Your answer has been cited in this paper that I was just reading, mentioning it here as a token of appreciation: arxiv.org/pdf/2005.10009.pdf $\endgroup$
    – NULL
    Jul 28 '20 at 19:59
31
$\begingroup$

Even the asymptotically sharp inequality ${2n \choose n} < 4^n \left/ \sqrt{\pi n} \right.$ has a short proof: $$ {2n \choose n} = \frac{4^n}{\pi} \int_{-\pi/2}^{\pi/2} \cos^{2n} x \phantom. dx < \frac{4^n}{\pi} \int_{-\pi/2}^{\pi/2} e^{-nx^2} dx < \frac{4^n}{\pi} \int_{-\infty}^{\infty} e^{-nx^2} dx = \frac{4^n}{\sqrt{\pi n}}. $$ In the first step, the formula for $\int_{-\pi/2}^{\pi/2} \cos^{2n} x \phantom. dx$ can be proved by induction via integration by parts, or using the Beta function.

The third step is clear, and the last step is the well-known Gaussian integral. So we need only justify the the second step.

There we need the inequality $\cos x \leq e^{-x^2/2}$, or equivalently $$ \log \cos x + \frac{x^2}{2} \leq 0, $$ for $\left|x\right| < \pi/2$, with equality only at $x=0$. This is true because $\log \cos x +\frac12 x^2$ is an even function of $x$ that vanishes at $x=0$ and whose second derivative $-\tan^2 x$ is negative for all nonzero $x \in (-\pi/2, \pi/2)$. QED

$\endgroup$
1
  • 9
    $\begingroup$ I'm not sure what counts as elementary in this game, but I would think the easiest proof that $\frac{1}{\pi} \int \cos^{2n} x dx = \binom{2n}{n}/4^n$ is to write $\cos x = (e^{ix} + e^{-ix})/2$ and expand $\cos^{2n}$ by the binomial theorem. $\endgroup$ Jul 1 '13 at 14:18
19
$\begingroup$

Erdos remarked somewhere the bound
$$ {{2n}\choose{n}}<\frac{4^n}{\sqrt{2n+1}}. $$ This can be established by induction: $$ {{2n+2}\choose{n+1}}=\frac{(2n+1)(2n+2)}{(n+1)(n+1)}{{2n}\choose{n}} $$ and if we have the bound for $n$, we only have to show $$ \frac{2(2n+1)}{(n+1)\sqrt{2n+1}}<\frac{4}{\sqrt{2n+3}} $$ which reduces to $4n^2+8n+3<4n^2+8n+4$.

$\endgroup$
1
  • $\begingroup$ This bound is pretty close to optimal because (unless I've computed badly) Stirling's approximation gives $4^n/\sqrt{\pi n}$. $\endgroup$ Jun 14 '13 at 13:26
14
$\begingroup$

Noam Elkies notes that there is a quick proof of $$\binom{2n}{n} \leq \frac{4^n}{\sqrt{\pi n}}$$ by writing $$\binom{2n}{n} = \frac{4^n}{\pi} \int_{-\pi/2}^{\pi/2} \cos^{2n} x dx$$ and bounding $\cos^2 x \leq e^{-x^2}$.

There is an equally good lower bound by a similar method: $$\int_{-\pi/2}^{\pi/2} \cos^{2n} x dx =\int_{-\pi/2}^{\pi/2} \frac{\sec^2 x dx}{(\tan^2 x+1)^{n+1}} = \int_{- \infty}^{\infty} \frac{du}{(1+u^2)^{n+1}} \geq \int_{- \infty}^{\infty} e^{-(n+1) u^2} du $$ so $$\binom{2n}{n} \geq \frac{4^n}{\sqrt{\pi (n+1)}}.$$ Here the inequality $\tfrac{1}{1+u^2} \geq e^{-u^2}$ follows from the standard bound $e^y \geq 1+y$ for $y\geq 0$.

$\endgroup$
7
$\begingroup$

We may prove without using integrals that $$ \frac1{\sqrt{\pi n}}\geqslant 4^{-n}{2n\choose n}\geqslant \frac{1}{\sqrt{\pi(n+1/2)}}.\quad\quad (1) $$ (1) is equivalent to $$2n\left(4^{-n}{2n\choose n}\right)^2=\frac12\prod_{k=2}^n \frac{(2k-1)^2}{2k(2k-2)}:=d_n\leqslant \frac2\pi\leqslant c_n\\:=(2n+1)\left(4^{-n}{2n\choose n}\right)^2=\prod_{k=1}^n\left(1-\frac1{4k^2}\right)$$ (the identities are straightforward by induction).

Denote $m:=2n+1$. It is not hard to show that $\sin mx=p_m(\sin x)$ for a polynomial of degree $m$ in $\sin x$. The roots of $p_m$ are $\sin \frac{k\pi}{2n+1}$ for $k=-n,\ldots,n$. Thus $$\sin (2n+1)x=(2n+1)\sin x\prod_{k=1}^n\left(1-\frac{\sin^2 x}{\sin^2 \frac{k\pi}{2n+1}}\right)$$ (the multiple $2n+1$ comes from dividing by $x$ and putting $x=0$). Put $x=\frac{\pi}{4n+2}$. Using the inequality $\sin tx\leqslant t\sin x$ (which may be proved, for example, by induction in $t=1,2,\ldots$ from the identity $\sin(t+1)x=\sin tx\cos x+\sin x\cos tx$) for $t=2k$ ($k=1,2,\ldots,n$) we get $$ 1\leqslant (2n+1)\sin\frac{\pi}{4n+2}\prod_{k=1}^n\left(1-\frac1{4k^2}\right)\leqslant \frac{\pi}{2}c_n,\quad c_n\geqslant \frac{2}\pi. $$ Analogously we get $$ \cos 2nx=\prod_{k=1}^n\left(1-\frac{\sin^2 x}{\sin^2 \frac{\pi(2k-1)}{4n}}\right). $$

Dividing by $1-\frac{\sin^2 x}{\sin^2 \frac{\pi}{4n}}$ and substituting $x=\frac{\pi}{4n}$ (for computing the LHS at this point use l'Hôpital rule) we get $$ n\tan\frac{\pi}{4n}\leqslant \prod_{k=2}^n\left(1-\frac1{(2k-1)^2}\right)=\frac1{2d_n},\quad d_n\leqslant \frac1{2n\tan \frac{\pi}{4n}}\leqslant \frac2\pi. $$

UPD. This is less or more equivalent to Yaglom brothers proof (1953), see their Russian paper (it contains also the derivation of identities $\sum 1/n^2=\pi^2/6$ and $\sum (-1)^{k-1}/(2k-1)=\pi/4$ using these trigonometric things.)

$\endgroup$
4
  • $\begingroup$ Nice proof! Is there an easy way to get the tight lower bound $1/\sqrt{\pi n+1}$? It has such a nice form.. $\endgroup$
    – aorq
    Jan 1 at 2:54
  • 1
    $\begingroup$ @aorq It is not so much tight. The sequence $4^{-n}{2n\choose n}\sqrt{n+c}$ eventually decreases if $c>1/4$ (this is straightforward: divide the squares of two consecutive terms and subtract 1) and its limit equals $1/\sqrt{\pi}$. Thus for large enough $n$ we get the upper bound $1/\sqrt{\pi (n+c)}$. For $c=1/\pi$ this just works from the very beginning. $\endgroup$ Jan 1 at 9:51
  • $\begingroup$ Yes, I know that it's tight in the weakest possible sense, namely equality for $n=0$ and poor otherwise. Shortly after I wrote my comment, I saw that $1/\sqrt{\pi(n+1/4)}$ was tighter in a more meaningful sense (on the other side), namely ever better as $n\to\infty$. Thanks for your explanation! $\endgroup$
    – aorq
    Jan 1 at 14:41
  • $\begingroup$ Warning: $1/\sqrt{\pi(n+1/4)}$ is an upper bound $\endgroup$ Jan 1 at 15:08
4
$\begingroup$

You may also prove ${2n\choose n}\sim \frac{4^n}{\sqrt{\pi n}}$ using the combinatorial meaning of ${2n\choose n}$ and the area-of-a-circle definition of $\pi$. That is probably the most elementary we can hope for.

First of all, if $a_n:=\sqrt{n+1/4}{2n\choose n}4^{-n}$ and $b_n:=\sqrt{n+1/2}{2n\choose n}4^{-n}$, we may check that $a_n\leqslant b_n$, $a_n$ increases and $b_n$ decreases, thus $a_n$, $b_n$ have a common positive finite limit which we denote $\alpha$, and $a_n\leqslant \alpha\leqslant b_n$. Since $b_n/a_n=1+O(1/n)$, we get $a_n=\alpha+O(1/n)$, and also $c_n=\alpha+O(1/n)$ where $c_n:=\sqrt{n}{2n\choose n}4^{-n}$.

We should prove that $\alpha=1/\sqrt{\pi}$.

Use the combinatorial identity $$4^{-n}\sum_{k=0}^n k{2k\choose k}(n-k){2(n-k)\choose n-k}=\frac{n(n-1)}8.\quad (\heartsuit)$$ LHS of $(\heartsuit)$ equals $$ \sum_{k=0}^n \sqrt{k(n-k)}c_kc_{n-k}=\sum_{k=0}^n \sqrt{k(n-k)}\left(\alpha^2+O\left(\frac1k+\frac1{n-k}\right)\right)\\=\alpha^2\sum_{k=0}^n\sqrt{k(n-k)}+O\left(n\sum_{k=0}^n\frac1{\sqrt{k(n-k)}}\right)=\alpha^2\cdot \frac{\pi n^2}8+o(n^2), $$ since the union of rectangles $[k,k+1]\times [0,\sqrt{k(n-k)}]$ approximates the upper semi-circle with the horizontal diameter $[0,n]$.

Thus $\alpha^2\pi/8=1/8$ and $\alpha=1/\sqrt{\pi}$.

You could use instead of $(\heartsuit)$ the more famous identity $$ 4^{-n}\sum_{k=0}^n {2k\choose k}{2(n-k)\choose n-k}=1 $$ this gives $\alpha^2\int_0^1\frac{dx}{\sqrt{x(1-x)}}=1$ (the integral equals $\pi$ of course, but this is less "elementary" then the area of a circle.)

This argument is similar to J. Wästlund's (An elementary proof of Wallis' product formula for $\pi$, 2007).

$\endgroup$
4
$\begingroup$

Since it gives tighter bounds, I will reproduce my answer from MathSE.


For $n\ge0$, we have (by cross-multiplication) $$ \begin{align} \left(\frac{n+\frac12}{n+1}\right)^2 &=\frac{n^2+n+\frac14}{n^2+2n+1}\\ &\le\frac{n+\frac13}{n+\frac43}\tag{1} \end{align} $$ Therefore, $$ \begin{align} \frac{\binom{2n+2}{n+1}}{\binom{2n}{n}} &=4\frac{n+\frac12}{n+1}\\ &\le4\sqrt{\frac{n+\frac13}{n+\frac43}}\tag{2} \end{align} $$ Inequality $(2)$ implies that $$ \boxed{\bbox[5pt]{\displaystyle\binom{2n}{n}\frac{\sqrt{n+\frac13}}{4^n}\text{ is decreasing}}}\tag{3} $$ For $n\ge0$, we have (by cross-multiplication) $$ \begin{align} \left(\frac{n+\frac12}{n+1}\right)^2 &=\frac{n^2+n+\frac14}{n^2+2n+1}\\ &\ge\frac{n+\frac14}{n+\frac54}\tag{4} \end{align} $$ Therefore, $$ \begin{align} \frac{\binom{2n+2}{n+1}}{\binom{2n}{n}} &=4\frac{n+\frac12}{n+1}\\ &\ge4\sqrt{\frac{n+\frac14}{n+\frac54}}\tag{5} \end{align} $$ Inequality $(5)$ implies that $$ \boxed{\bbox[5pt]{\displaystyle\binom{2n}{n}\frac{\sqrt{n+\frac14}}{4^n}\text{ is increasing}}}\tag{6} $$ Note that the formula in $(3)$, which is decreasing, is bigger than the formula in $(6)$, which is increasing. Their ratio tends to $1$; therefore, they tend to a common limit, $L$.


Theorem $1$ from this answer says $$ \lim_{n\to\infty}\frac{\sqrt{\pi n}}{4^n}\binom{2n}{n}=1\tag{7} $$ which means that $$ \begin{align} L &=\lim_{n\to\infty}\frac{\sqrt{n}}{4^n}\binom{2n}{n}\\ &=\frac1{\sqrt\pi}\tag8 \end{align} $$ Combining $(3)$, $(6)$, and $(8)$, we get $$ \boxed{\bbox[5pt]{\displaystyle\frac{4^n}{\sqrt{\pi\!\left(n+\frac13\right)}}\le\binom{2n}{n}\le\frac{4^n}{\sqrt{\pi\!\left(n+\frac14\right)}}}}\tag9 $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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