1
$\begingroup$

This is sort of a cross-post from here, since I'm looking for a more mathematical proof.

I was recently learning about binomial coefficients and was wondering about how to disprove 2nCn (or the central binomial coefficient) not being lower-bounded by 4^n; in other words:

$$\binom{2n}{n} \notin \Omega (4^n)$$

Some extremely generous bounds can be easily constructed, such as the following:

$$\frac{4^n}{2n+1} \leq \binom{2n}{n} \leq 4^n \text{ for all } n \geq 1$$

I sought to prove by contradiction, so to assume:

$$\exists c_1 \text{ or } c_2 : 0 \lt c_14^n \leq \frac{4^n}{2n+1} \leq c_24^n \leq \binom{2n}{n} \leq 4^n$$

Clearly, $c_1$ cannot exist, since $\lim_{n \rightarrow \infty}{\frac{1}{2n + 1}} = 0$. It can also be seen that $c_2 \in (0,1]$. And... I'm stuck. Intuitively, it seems rather obvious that $c_2$ cannot exist.

I am aware a similar question has been asked here, but there wasn't really a proof provided. I'm also aware that you could prove $\lim_{n \rightarrow \infty}\frac{\binom{2n}{n}}{4^n} = 0$, but I was wondering if there was another way to do so - particularly, by proving that $c_2$ cannot exist.

$\endgroup$
1
$\begingroup$

You can prove by induction on $n\geq 1$ that $\binom{2n}{n} \leq \frac{4^n}{\sqrt{n}}.$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.