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

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}$.
