Prove $2^n$ is smaller than binomial coefficent of $2n$ over $n$

Question

I need to show that $\binom{2n}{n} \geq 2^n$.

I'm required to do this by using induction.

For $n=1$ this is rather easy.

I just don't get very far when going to the next step for $n+1$. Is there a way to write this as a sum, or is there another easy way to do that?

Answer 1

Hint: $$\binom{2n+2}{n+1}=\frac{(2n+2)(2n+1)}{(n+1)^2}\binom{2n}{n}$$ So it's sufficient to show that $$\frac{(2n+2)(2n+1)}{(n+1)^2}=\frac{2(2n+1)}{n+1}\ge 2$$ for sufficiently large $n$.

Answer 2

For the inductive step it is $\binom{2n+2}{n+1}=\binom{2n}{n}\cdot\frac{(2n+2)(2n+1)}{(n+1)^2}\geq 2^n\cdot \frac{2(n+1)(2n+1)}{(n+1)^2}$

by the inductive claim.

Furthermore it is $\frac{2(2n+1)}{n+1}>\frac{2(n+1)}{n+1}=2$.

So: $\binom{2n+2}{n+1}\geq 2^n\cdot 2=2^{n+1}$