How to prove through induction

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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.