# Proof of $(2n)!/(n!)^2\le2^{2n}$ by mathematical induction?

How do I approach this problem using mathematical induction?

$$\frac{(2n)!}{(n!)^2} \leq 2^{2n}$$

-
You should verify it for $n=1$. Then show that when you assume it's true for $n=k$ it also holds for $n=k+1$. Or just realize the RHS is the sum of the binomial coefficients in the $2n$'th row of Pascal's triangle, and the LHS is one such element. – mathmath8128 Dec 6 '11 at 4:09

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

-
Perhaps we can use induction to first show the binomial theorem. :-) [+1] – Srivatsan Dec 6 '11 at 4:27
Zev how did you come up with (2k+1)(2k+2)/(k+1)^2? – Anas_my Dec 6 '11 at 4:51
@Anas_my: He wanted a factor that would convert $\frac{(2k)!}{(k!)^2}$ to the next step up, $\frac{(2(k+1))!}{((k+1)!)^2}$. – Brian M. Scott Dec 6 '11 at 4:56
@BrianM.Scott: How did you come up with that factor? – Anas_my Dec 6 '11 at 5:38
@Anas_my: $(2(k+1))!=(2k+2)!=(2k+2)(2k+1)(2k)!$, and $(k+1)!=(k+1)k!$, so $$\frac{(2(k+1))!}{(k+1)!(k+1)!}=\frac{(2k+2)(2k+1)(2k)!}{(k+1)k!(k+1)k!}=\frac{‌​(2k+2)(2k+1)}{(k+1)^2}\cdot\frac{(2k)!}{k!k!}$$. – Brian M. Scott Dec 6 '11 at 5:55

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

-