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.
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 $.
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.
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.
