The asymptotic value of 2n choose n

2017-04-29

Tagged: math

What is the asymptotic value of (2nn){2n \choose n} as nn goes to infinity?

There’s a stupid solution that involves plugging in Stirling’s approximation three times and cleaning up the ensuing mess, but I thought of a better solution.

Let’s start by figuring out the ratio of two adjacent terms. Taking n=4,5n = 4, 5 as an example, we have:

(84)=8!4!4!{8 \choose 4} = \frac{8!}{4!4!}

(105)=10!5!5!=(84)⋅10⋅95⋅5{10 \choose 5} = \frac{10!}{5!5!} = {8 \choose 4} \cdot \frac{10 \cdot 9}{5 \cdot 5}

So it seems that as we increment nn, we’re multiplying by 2n(2n−1)n2≈4\frac{2n(2n-1)}{n^2} \approx 4. Therefore, the dominant term in the asymptotic growth rate is 4n4^n.

Can we do better? Yes. Let’s take a closer look at the approximation we made in the last step.

The approximation we took was to multiply by 2n2n−1\frac{2n}{2n-1} and pretend it didn’t happen. And that’s for a single step, for n→n+1n \rightarrow n+1. When you aggregate all of these small errors from 1 to nn, you get an extended product:

P=21⋅43⋅65⋅87⋅⋅⋅2n2n−1P = \frac{2}{1} \cdot \frac{4}{3} \cdot \frac{6}{5} \cdot \frac{8}{7}\cdot\cdot\cdot \frac{2n}{2n-1}

So we’re overestimating by a factor of PP. How can we estimate the value of this product? Well, it would be nice if we could cancel out the numerator and denominator of adjacent terms… What if we take the complementary series to fill in the gaps?

P′=32⋅54⋅76⋅98⋅⋅⋅2n−12n−2P' = \frac{3}{2} \cdot \frac{5}{4} \cdot \frac{7}{6} \cdot \frac{9}{8}\cdot\cdot\cdot \frac{2n-1}{2n-2}

P⋅P′=21⋅32⋅43⋅54⋅⋅⋅2n−12n−2⋅2n2n−1=2nP \cdot P' = \frac{2}{1} \cdot \frac{3}{2} \cdot \frac{4}{3} \cdot \frac{5}{4}\cdot\cdot\cdot \frac{2n-1}{2n-2} \cdot \frac{2n}{2n-1} = 2n

By multiplying these two series together, everything cancels out perfectly, in a zipper-like fashion. Our next approximation is to say that, since these two infinite series are complementary, they each contribute a half of the final product. Each component series is therefore worth P≈P′≈2nP \approx P' \approx \sqrt{2n}, and our improved asymptotic value is 4n2n\frac{4^n}{\sqrt{2n}}.

It’s definitely not true that the two halves are equal in value, though. As it turns out, there’s an infinite series that describes the divergence between these two halves: the Wallis product. There’s a nifty proof of this product by Euler - see the Wikipedia article for details.

W=PP′=21⋅23⋅43⋅45⋅65⋅67⋅⋅⋅=π2W = \frac{P}{P'} = \frac{2}{1} \cdot \frac{2}{3} \cdot \frac{4}{3} \cdot \frac{4}{5} \cdot \frac{6}{5} \cdot \frac{6}{7} \cdot\cdot\cdot = \frac{\pi}{2}

Using the Wallace product, we can upgrade our approximation to an equality: P⋅P′⋅W=P2=2n⋅π2=πnP \cdot P' \cdot W = P^2 = 2n \cdot \frac{\pi}{2} = \pi n

The actual asymptotic value is therefore 4nπn\frac{4^n}{\sqrt{\pi n}}. This value can be confirmed by the brute-force Stirling’s approximation solution.