Big O of binomial coefficient

Question

I found a question online, but I can't figure out a way to prove that

\begin{align} \begin{pmatrix} n \newline \frac n2\end{pmatrix}= O(2^n) \end{align}

Is there an easy way to proof this?

Thanks :)

Answer 1

Even if you want to show that, in fact, $$\binom{n}{\lfloor n/2\rfloor}=\mathop{O}\left(\frac{2^n}{\sqrt{n}}\right),$$ then there is still an easy induction proof that does not need a Stirling formula. Namely, prove by induction that $$\binom{2n}{n}\le\frac{2^{2n}}{\sqrt{n+1}}$$ and combine it with the fact that $$\binom{2n-1}{n-1}=\frac{1}{2}\binom{2n}{n}.$$

In fact, a very similar estimate could be proved even without induction. Let’s start with the inequality $$ \frac{1}{2}\cdot \frac{3}{4}\cdot\ldots\cdot \frac{2n-1}{2n} < \frac{2}{3}\cdot \frac{4}{5}\cdot\ldots\cdot \frac{2n}{2n+1} $$ for $n\ge 1$, easy to see since each factor is increased from the left hand side to the right hand side.

Dividing LHS by RHS, we obtain $$ \frac{((2n-1)!!)^2(2n+1)}{2^{2n}(n!)^2}< 1. $$ Now substitute $(2n-1)!!=\dfrac{(2n)!}{2^{n}n!}$ to get $$ 1>\frac{((2n)!)^2(2n+1)}{2^{4n}(n!)^4}=\frac{2n+1}{2^{4n}}\binom{2n}{n}^2, $$ or, equivalently, $$ \binom{2n}{n}<\frac{2^{2n}}{\sqrt{2n+1}}. $$