Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How do I approach this problem using mathematical induction?

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

share|improve this question
    
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

2 Answers 2

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

share|improve this answer
    
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.$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.