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

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s