The middle binomial coefficient

The previous post contained an interesting observation:

Is it true more generally that

for largen? Sorta, but the approximation gets better if we add a correction factor.

If we square both sides of the approximation and move the factorials to one side, the question becomes whether

Now the task becomes to estimate the middle coefficient in when we apply the binomial theorem to (x +y)²ⁿ.

A better approximation for the middle binomial coefficient is

Now the right hand side is the first term of an asymptotic series for the left. The ratio of the two sides goes to 1 as n .

We could prove the asymptotic result using Stirling's approximation, but it's more fun to use a probability argument.

Let X be a binomial random variable with distribution B(2n, 1/2). As n grows, X converges in distribution to a normal random variable with the same mean and variance, i.e. with = n and ^2 = n/2. This says for large n,

The argument above only gives the first term in the asymptotic series for the middle coefficient. If you want more terms in the series, you'll need to use more terms in Stirling's series. If we add a couple more terms we get

Let's see how much accuracy we get in estimating 52 choose 26.

from scipy.special import binomfrom numpy import pi, sqrtn = 26exact = binom(2*n, n)approx1 = 4**n/sqrt(pi*n)approx2 = approx1*(1 - 1/(8*n))approx3 = approx1*(1 - 1/(8*n) + 1/(128*n**2))for a in [approx1, approx2, approx3]: print(exact/a)

This prints

0.99520414092662931.00001189039970481.0000002776131290

and so we see substantial improvement from each additional term. This isn't always the case with asymptotic series. We're guaranteed that for a fixed number of terms, the relative error goes to zero as n increases. For a fixed n, we do not necessarily get more accuracy by including more terms.

Related posts

• Rise and fall of binomial coefficients
• Combinators and Catalan numbers

The post The middle binomial coefficient first appeared on John D. Cook.