Big-O analysis of a combination function

Question

Prove that $$\binom{2n}{n} \in O\left(4^n/\sqrt{n}\right) $$ I am not familiar with markdown syntax so sorry for the formula display

Answer 1

In the comments you can find links to an argument using Stirling's approximation and an argument using an integral formula; here's a much more elementary argument (which gives a worse bound). Write $a_n = {2n \choose n}$. We have

$$\frac{a_{n+1}}{a_n} = \frac{(2n+2)! n!^2}{(2n)! (n+1)!^2} = \frac{4n+2}{n+1} = 4 - \frac{2}{n+1}$$

which gives

$$a_n = \prod_{i=1}^n \left( 4 - \frac{2}{i} \right) = 4^n \prod_{i=1}^n \left( 1 - \frac{1}{2i} \right) = 4^n \left( 1 - \frac{1}{2} \right) \left( 1 - \frac{1}{4} \right) \dots \left( 1 - \frac{1}{2n} \right).$$

Squaring $\frac{a_n}{4^n}$ gives

$$\begin{align*} \prod_{i=1}^n \left( 1 - \frac{1}{2i} \right)^2 & \le \prod_{i=1}^n \left( 1 - \frac{1}{2i-1} \right) \left( 1 - \frac{1}{2i} \right) \\ &= \left( 1 - \frac{1}{2} \right) \left( 1 - \frac{1}{3} \right) \dots \left( 1 - \frac{1}{2n-1} \right) \left( 1 - \frac{1}{2n} \right) \\ &= \frac{1}{2n} \end{align*}.$$

This gives

$$\boxed{ {2n \choose n} \le \frac{4^n}{\sqrt{2n}} }$$

although that constant $2$ in the denominator is not best possible. Doing this argument more carefully can get the best constant, which is $\pi$, using the Wallis product, as explained on Wikipedia.

Alternatively, the inequality $1 - x \le \exp(-x)$ gives

$$a_n \le 4^n \exp \left( \sum_{i=1}^n - \frac{1}{2i} \right) = 4^n \exp \left( - \frac{H_n}{2} \right)$$

where $H_n$ is the $n^{th}$ harmonic number. The elementary inequality $H_n \ge \log n$ gives ${2n \choose n} \le \frac{4^n}{\sqrt{n}}$ which is a bit worse, but this argument is very general. We could do a more careful analysis here by taking logarithms.

There's also a conceptual interpretation of the true asymptotic ${2n \choose n} \sim \frac{4^n}{\sqrt{\pi n}}$ that comes from applying the central limit theorem to the binomial distribution $\text{Bin} \left( 2n, \frac{1}{2} \right)$. I think this is in some sense the best explanation of that funny $\sqrt{\pi n}$.