How do I approach this problem using mathematical induction?
$\frac{(2n)!}{(n!)^2} \leq 2^{2n}$
How do I approach this problem using mathematical induction?
$\frac{(2n)!}{(n!)^2} \leq 2^{2n}$
Base case (proving the statement is true for $n=1$): $\frac{(2)!}{(1!)^2} =\frac{2}{1^2}=2\leq 4=2^{2}\qquad \checkmark$
Induction step (proving that, if the statement is true for $n=k$, then it is true for $n=k+1$):
If the statement is true for $n=k$, that is if $\frac{(2k)!}{(k!)^2} \leq 2^{2k},$ then multiplying both sides by $\frac{(2k+1)(2k+2)}{(k+1)^2}$, we get
$\frac{(2k)!}{(k!)^2} \cdot\frac{(2k+1)(2k+2)}{(k+1)^2}\leq 2^{2k}\cdot\frac{(2k+1)(2k+2)}{(k+1)^2}.$ But the left side is just $\frac{(2k)!}{(k!)^2} \cdot \frac{(2k+1)(2k+2)}{(k+1)^2}=\frac{(1\cdot2\cdot \ldots \cdot 2k)(2k+1)(2k+2)}{(1\cdot2\cdot \ldots \cdot k)(1\cdot2\cdot \ldots \cdot k)(k+1)(k+1)}=\frac{(2k+2)!}{((k+1)!)^2},$ so we have shown that $\frac{(2k+2)!}{((k+1)!)^2}\leq 2^{2k}\times \frac{(2k+1)(2k+2)}{(k+1)^2}.$
Because $(2k+1)(2k+2)\leq (2k+2)(2k+2)=4(k+1)^2,$ we have that
$\frac{(2k+2)!}{((k+1)!)^2}\leq 2^{2k}\times 4=2^{2k+2},$ which is what we wanted, i.e. that the statement is true for $n=k+1$.
A simpler approach, not using mathematical induction, would be to use the binomial theorem, $2^{2n}=(1+1)^{2n}=\sum_{k=0}^{2n}\binom{2n}{k}.$ Then note that $\binom{2n}{n}=\frac{(2n)!}{n!\; n!}=\frac{(2n)!}{(n!)^2}$ and that $\binom{2n}{k}\geq0$ for all $0\leq k\leq 2n$.
A mechanical approach: $\frac{(2n+2)!}{(n+1)!(n+1)!}=\frac{(2n)!}{n!n!} \frac{(2n+1)(2n+2)}{(n+1)(n+1)}.$ Note that $\frac{(2n+1)(2n+2)}{(n+1)(n+1)}=2\frac{2n+1}{n+1}<2^2.$