How to prove through induction How can I prove by induction that 
$$\binom{2n}n<4^n\;?$$
I have solved for the base case, $n=1$, and have formulated the induction hypothesis. I was thinking about Pascal's identity for the rest, but have not been able to come up with a way to use it.
 A: And, of course,
for a non-inductive,
non-original proof:
$\binom{2n}{n}
<\sum_{k=0}^{2n} \binom{2n}{k}
=(1+1)^{2n}
=2^{2n}
=4^n
$.
A: HINT: Pascal’s identity will work. You get
$$\binom{2n+2}{n+1}=\binom{2n+1}{n+1}+\binom{2n+1}n\;.$$
Now notice that $\binom{2n+1}n=\binom{2n+1}{n+1}$, so you can rewrite this as
$$\binom{2n+2}{n+1}=2\binom{2n+1}{n+1}\;.$$
Now apply Pascal’s identity again, and use the fact that the central binomial coefficients are the largest for a given upper number.
A: First, show that this is true for $n=1$:
$\binom{2}{1}<4^{1}$
Second, assume that this is true for $n$:
$\binom{2n}{n}<4^{n}$
Third, prove that this is true for $n+1$:
$\binom{2n+2}{n+1}=$
$\frac{(2n+2)!}{(n+1)!\cdot(n+1)!}=$
$\frac{(2n)!\cdot(2n+1)\cdot(2n+2)}{(n)!\cdot(n+1)\cdot(n)!\cdot(n+1)}=$
$\frac{(2n)!\cdot(2n+1)\cdot(2n+2)}{(n)!\cdot(n)!\cdot(n+1)\cdot(n+1)}=$
$\frac{(2n)!}{(n)!\cdot(n)!}\cdot\frac{(2n+1)\cdot(2n+2)}{(n+1)\cdot(n+1)}=$
$\color{red}{\binom{2n}{n}}\cdot\frac{(2n+1)\cdot(2n+2)}{(n+1)\cdot(n+1)}\color{red}<$
$\color{red}{4^{n}}\cdot\frac{(2n+\color{blue}{1})\cdot(2n+2)}{(n+1)\cdot(n+1)}\color{blue}<$
$4^{n}\cdot\frac{(2n+\color{blue}{2})\cdot(2n+2)}{(n+1)\cdot(n+1)}=$
$4^{n}\cdot\frac{2(n+1)\cdot2(n+1)}{(n+1)\cdot(n+1)}=$
$4^{n}\cdot2\cdot2=$
$4^{n}\cdot4=$
$4^{n+1}$

Please note that the assumption is used only in the part marked red.
