4
$\begingroup$

How do I approach this problem using mathematical induction?

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

  • 0
    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.2011-12-06

2 Answers 2

5

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

  • 0
    @BrianM.Scott Awesome! thank you.2011-12-06
3

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