## Bounds for central binomial coefficients

Let $n$ be a positive integer. The binomial coefficient ${2n \choose n}$ is called a central binomial coefficient. Several bounds for these coefficients are known and the more advanced ones are commonly derived from Stirling’s formula for factorials or from Wallis’ product for $\pi$. This post presents an alternative and self-contained elementary proof of the bounds

$\displaystyle \frac{4^n}{\sqrt{(n+\frac{1}{2})\pi}} < {2n \choose n} < \frac{4^n}{\sqrt{n\pi}}$.

Define a function $f$ by

$\displaystyle f(x) = \cos(x)^n e^{n x^2/2}$

and take $x\in[0, \pi/2)$. From $f(x) \geq 0$ and $\tan(x)\geq x$ it follows that

$\displaystyle f'(x) = n f(x)\left(x - \tan(x)\right) \leq 0$.

So $f$ is non-increasing on this interval and therefore $f(x) \leq f(0)=1$ or

$\displaystyle \cos(x)^n \leq e^{-n x^2/2}$.

This inequality clearly also holds at the endpoint $x=\pi/2$ and since both sides are symmetric in $x$ it holds throughout the interval $[-\pi/2, \pi/2]$. (It suggests that $\cos(x)^n$ closely resembles a normal distribution on this interval.) Integration of the inequality above leads to

$\displaystyle \int_{-\pi/2}^{\pi/2}\cos(x)^n dx \leq \int_{-\pi/2}^{\pi/2}e^{-n x^2/2}dx < \int_{-\infty}^{\infty}e^{-n x^2/2}dx$.

Both the far left and right hand sides of these inequality can be computed explicitly. Starting with the right hand side let

$\displaystyle b_n=\int_{-\infty}^{\infty}e^{-n x^2/2}dx$.

Then

$\displaystyle b_n^2=\int_{-\infty}^{\infty}e^{-n x^2/2}dx \int_{-\infty}^{\infty}e^{-n y^2/2}dy=\iint_{-\infty}^{\infty}e^{-n (x^2+y^2)/2}dx dy$

$\displaystyle =2 \pi \int_0^{\infty} r e^{-n r^2/2}dr = \frac{2\pi}{n}$

And so $b_n=\sqrt{\frac{2\pi}{n}}$. To evaluate the left hand side let

$\displaystyle a_n=\int_{-\pi/2}^{\pi/2}\cos(x)^n dx.$

By explicit computation we find $a_0=\pi$ and $a_1=2$. The other values can be found by a recursive relation that follows from partial integration. For positive $n$ we have

$\displaystyle a_{n+1}=\int_{-\pi/2}^{\pi/2}\cos(x)^n \cos(x)dx=n\int_{-\pi/2}^{\pi/2}\cos(x)^{n-1} \sin(x)^2dx$

$\displaystyle =n\int_{-\pi/2}^{\pi/2}\cos(x)^{n-1}\left(1- \cos(x)^2\right)dx=n(a_{n-1}-a_{n+1})$

and therefore the recursion $a_{n+1}=\frac{n}{n+1}a_{n-1}$. Using this recursion one can check that the even and odd entries of the sequence $a$ are given respectively by

$\displaystyle a_{2n}=4^{-n}{2n \choose n}\pi$

$\displaystyle a_{2n+1}=\frac{2^{2n+1}}{{2n \choose n}(2n +1)}$.

Putting all results sofar together we find for positive even integers $2n$

$\displaystyle 4^{-n}{2n \choose n}\pi<\sqrt{\frac{2\pi}{2n}}$

$\displaystyle {2n \choose n}<\frac{4^n}{\sqrt{n \pi}}$

and for odd integers $2n+1$

$\displaystyle \frac{2^{2n+1}}{{2n \choose n}(2n+1)} < \sqrt{\frac{2\pi}{2n+1}}$

$\displaystyle \frac{4^n}{\sqrt{(n+\frac{1}{2})\pi}} < {2n \choose n}$.