asymptotics of central binomial coefficient

By making use of the expression

$$4^{-n}\left(\genfrac{}{}{0pt}{}{2n}{n}\right)=\prod _{m=1}^n\frac{2m-1}{2m},$$

we may obtain estimates of the central binomial coefficient $\left(\genfrac{}{}{0pt}{}{2n}{n}\right)$ for large values of $n$. We begin by making some elementary algebraic manipulations of this product:

$$4^{-n}(2n+1)\left(\genfrac{}{}{0pt}{}{2n}{n}\right)=\frac{(2n+1)\prod _{m=1}^n(2m-1)}{{\prod }_{m=1}^{n}2m}=\frac{\prod _{m=1}^n(2m+1)}{{\prod }_{m=1}^{n}2m}=\prod _{m=1}^n\frac{2m+1}{2m}$$

Then we multiply this by our previous expression, factor-by-factor:

$${16}^{-n}(2n+1){\left(\genfrac{}{}{0pt}{}{2n}{n}\right)}^2=\prod _{m=1}^n\frac{(2m+1)(2m-1)}{{(2m)}^2}.$$

With a bit of rearrangement and manipulation, this gives us the following formula for the central binomial coefficient,

$$\left(\genfrac{}{}{0pt}{}{2n}{n}\right)=\frac{4^n}{\sqrt{2n+1}}\sqrt{\prod _{m=1}^n\left(1-\frac{1}{4m^2}\right)},$$

which we shall examine to obtain estimates of the central binomial coefficient for large $n$.

To make use of this formula, we make two key observations about the product which appears on the right-hand side. First, since each of the terms in the product lies between $0$ and $1$, the product is an decreasing function of $n$, Thus, we have

$$4^{-a}\sqrt{2a+1}\left(\genfrac{}{}{0pt}{}{2a}{a}\right)>4^{-b}\sqrt{2b+1}\left(\genfrac{}{}{0pt}{}{2b}{b}\right)$$

when . Secondly, the product converges in the limit $n\to \mathrm{\infty }$. In fact, it turns out to be Wallis’ product for $\pi$, so we have

$$\underset{n\to \mathrm{\infty }}{lim}{4}^{-n}\sqrt{2n+1}\left(\genfrac{}{}{0pt}{}{2n}{n}\right)=\sqrt{\frac{2}{\pi }}.$$

This limit may be reread as an approximate formula when $n$ is large:

$$\left(\genfrac{}{}{0pt}{}{2n}{n}\right)\approx \sqrt{\frac{2}{\pi }}\frac{4^n}{\sqrt{2n+1}}$$

As an example, let us consider the case $n=10$. The exact answer is $\left(\genfrac{}{}{0pt}{}{20}{10}\right)=184756$. The approximate answer is $(4^{10}\sqrt{2}/\sqrt{21\pi })=182570.38\mathrm{\dots }$, which agrees with the exact answer to a percent. Also note that the estimate is smaller than the exact answer — this is a general feature which is due to the observation made above that the product is an decreasing function of $n$. Moreover, this observation also implies that the percentage error decreases as $n$ increases; in particular, the approximation is good within a percent when $n>10$.

It is worth noting that same result can be obtained from Stirling’s formula. In fact, one can deduce Stirling’s formula by a similar line of reasoning.

With a little more work, wee can improve our approximation. We begin by considering the product

$$\prod _{m=1}^n\frac{64m^2-9}{64m^2-25}.$$

On the one hand, we can evaluate this product by factoring the numerator and denominator and cancelling terms:

${\displaystyle \prod _{m=1}^n}{\displaystyle \frac{64m^2-9}{64m^2-25}}$ $={\displaystyle \prod _{m=1}^n}{\displaystyle \frac{(8m-3)(8m+3)}{(8m-5)(8m+5)}}$

$={\displaystyle \frac{5\cdot 11}{3\cdot 13}}\cdot {\displaystyle \frac{13\cdot 19}{11\cdot 21}}\cdot {\displaystyle \frac{21\cdot 27}{19\cdot 29}}\mathrm{\cdots }\mathrm{\cdots }{\displaystyle \frac{(8n-11)(8n+5)}{(8n-13)(8n-3)}}\cdot {\displaystyle \frac{(8n-3)(8n+3)}{(nm-5)(8n+5)}}$

$={\displaystyle \frac{5}{3}}\cdot {\displaystyle \frac{8n+3}{8n+5}}$

From this expression, it follows that the product converges to $5/3$ as $n\to \mathrm{\infty }$. On the other hand, we can multiply this product by the product we obtained earlier termwise:

$\left({\displaystyle \prod _{m=1}^n}{\displaystyle \frac{64m^2-9}{64m^2-25}}\right)\left({\displaystyle \prod _{m=1}^n}\left(1-{\displaystyle \frac{1}{4m^2}}\right)\right)$ $={\displaystyle \prod _{m=1}^n}{\displaystyle \frac{64m^2-9}{64m^2-25}}\cdot {\displaystyle \frac{4m^2-1}{4m^2}}$

$={\displaystyle \prod _{m=1}^n}{\displaystyle \frac{256m^4-100m^2+9}{256m^4-100m^2}}$

$={\displaystyle \prod _{m=1}^n}\left(1+{\displaystyle \frac{9}{256m^4-100m^2}}\right)$

By taking limits on both sides, we conclude that

$$\prod _{m=1}^{\mathrm{\infty }}\left(1+\frac{9}{256m^4-100m^2}\right)=\frac{10}{3\pi }.$$

Embracing our earlier formula for the central binomial coefficient with both hands, we obtain

$${16}^{-n}\cdot \frac{80n^2+70n+15}{24n+15}{\left(\genfrac{}{}{0pt}{}{2n}{n}\right)}^2=\prod _{m=1}^n\left(1+\frac{9}{256m^4-100m^2}\right).$$

Juggling terms from one hand to the other, we obtain a new formula for the central binomial coefficient:

$$\left(\genfrac{}{}{0pt}{}{2n}{n}\right)=4^n\sqrt{\frac{24n+15}{80n^2+70n+15}}\sqrt{\prod _{m=1}^n\left(1+\frac{9}{256m^4-100m^2}\right)}$$

Despite the increase in complexity, this formula is actually an improvement over the old formula. The reason for this is that the product converges more rapidly because the polynomial in the denominator is now of the fourth order.

As before, we may take the limit $n\to \mathrm{\infty }$:

$$\underset{n\to \mathrm{\infty }}{lim}{4}^{-n}\sqrt{\frac{16n^2+14n+3}{8n+5}}\left(\genfrac{}{}{0pt}{}{2n}{n}\right)=\sqrt{\frac{2}{\pi }}$$

This gives us a new, improved asymptotic formula:

$$\left(\genfrac{}{}{0pt}{}{2n}{n}\right)\approx \sqrt{\frac{2}{\pi }}{\mathrm{\hspace{0.17em}4}}^n\sqrt{\frac{8n+5}{16n^2+14n+3}}$$

To see just how good this formula is, let us revisit the case $n=10$. Now, we get the approximation $(4^{10}\sqrt{170/1743\pi })=184756.93\mathrm{\dots }$. Because the terms in the new product are greater than unity, the approximation is an overestimate, so we round it down to $184756$, which just so happens to be the exact answer. The approximation is that good!

Title	asymptotics of central binomial coefficient
Canonical name	AsymptoticsOfCentralBinomialCoefficient
Date of creation	2013-03-22 17:40:50
Last modified on	2013-03-22 17:40:50
Owner	rspuzio (6075)
Last modified by	rspuzio (6075)
Numerical id	18
Author	rspuzio (6075)
Entry type	Result
Classification	msc 11B65
Classification	msc 05A10
Related topic	CatalanNumbers