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