Show that for any integer $n\ge5$, the inequality ${2n \choose n}>3^n$ holds.

Question

I used induction, but got stuck at the last step. By cancelling common factors in the expanded $2n$ choose $n$, I got a simpler equation that didn't make sense.How do i prove this inequality?

Answer 1

The main step is to prove for $n+1$ then

$${2(n+1)\choose n+1}=\frac{(2n+2)!}{(n+1)!(n+1)!}=\frac{(2n+2)(2n+1)}{(n+1)^2}{2n\choose n}=\frac{2(2n+1)}{(n+1)}{2n\choose n}$$

Using the hypothesis

$${2(n+1)\choose n+1}>\frac{2(2n+1)}{(n+1)}\cdot 3^n$$

but

$$\frac{2(2n+1)}{n+1}=\frac{4n+2}{n+1}=\frac{3(n+1)+(n-1)}{n+1}=3+\frac{n-1}{n+1}>3$$

so,

$${2(n+1)\choose n+1}>\frac{2(2n+1)}{(n+1)}\cdot 3^n>3\cdot 3^n=3^{n+1}$$

Answer 2

Here's a slightly goofier approach:

By the binomial theorem, we have $4^n=\sum_{k=0}^{2n} \binom{2n}{k}$. Since $\binom{2n}{n}$ is the largest of these $2n+1$ summands, it is at least as large as the average of the summands. So $\binom{2n}{n} \geq \frac{4^n}{2n+1}$.

I claim that $\frac{4^n}{2n+1}>3^n$ for all $n \geq 11$. This can be proved by induction: it is true for $n=11$, and if it is true for some fixed $n\geq 11$, then $$ \frac{4^{n+1}}{3^{n+1}}=\frac{4}{3}\frac{4^n}{3^n}>\frac{4}{3}(2n+1)>2n+3 $$ (this last inequality holds for all $n \geq 3$).

So the result is true for $n \geq 11$. It only remains to check that it is true for $n=5,6,7,8,9,10$, which is a straightforward computation.

Answer 3

Since $\binom{2m+2n}{m+n}\ge\binom{2m}m\binom{2n}n,$ the set $\{n:\binom{2n}n\ge3^n\}$ is closed under addition. Therefore, in order to show that the inequality holds for all $n\ge5,$ it's enough to verify it for $n=5,6,7,8,9.$

Answer 4

Two useful identities: $$\binom{n}{k} = \frac{n}{k}\binom{n-1}{k-1}$$ $$\binom{n}{k} = \binom{n}{n-k}$$ Applied here. $$\binom{2n+2}{n+1}=\frac{2n+2}{n+1}\binom{2n+1}{n}=\frac{2n+2}{n+1}\binom{2n+1}{n+1}=\frac{(2n+2)(2n+1)}{(n+1)^2}\binom{2n}{n}$$

Then just get lower bounds $$\frac{(2n+2)(2n+1)}{(n+1)^2} \geq 3$$ which is straight forwards.

Answer 5

Let $a=\frac{(2n)!}{n!n!}$. Given that $a>3^n$ show $\frac{(2n+1)(2n+2)}{(n+1)^2}a > 3^{n+1}$.

$\frac{4n^2+7n+2}{n^2+2n+1}a > 3*3^n$. Since $a>3^n$ it is sufficient to show that $\frac{4n^2+7n+2}{n^2+2n+1} > 3$. $$ 4n^2+7n+2 > 3n^2+6n+3$$$$ n^2+n-1 > 0$$ which is clearly true for $n\geq 5$