Big-O analysis of a combination function 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
 A: 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}$.
