# First Year Calculus Course Mathematical Induction Problem

1. Mar 3, 2013

### MP14

Prove by mathematical induction:

(2n)! < (2^(2n))*(n!)^2 , for all n=2,3,4...

I know that to start you must prove that it is true for n=2,

(2*2)! = 24 < 64 = (2^4)(2!)^2

Then you assume that n=k and show tha n=k implies that n=(k+1)

(2k)! < (2^(2k))*(k!)^2

... At this point I am completely lost, I don't know where to go from here to turn it into (k+1)
Any help would be greatly appreciated.
Thanks!

2. Mar 3, 2013

### Dick

But what factor does each side increase when you go from k to k+1?

3. Mar 3, 2013

### MP14

I'm not too sure... I tried multiplying both sides by 4, because if you do that you would end up getting:

4(2k)! < 4(2^(2k))*(k!)^2
4(2k)! < (2^2)*(2^(2k))*(k!)^2
4(2k)! < (2^(2k+2))*(k!)^2
4(2k)! < (2^(2(k+1)))*(k!)^2

But then that still leaves me with (2k) on the left side and (k) on the right.
Any suggestions? Am I on the right track?

4. Mar 3, 2013

### Dick

It might be easier to see another way (2(k+1))!=A*(2k)! What's A? And 2^(2(k+1))*(k+1)!^2=B*(2^k*k!^2). What's B?

5. Mar 3, 2013

### MP14

Solving for A I get A = 1 + 1/k, and for B I get B = 4(k+1)^2.
I don't think that we can multiply the inequality by k, so is there another way to approach this?

6. Mar 3, 2013

### Dick

B is right. A isn't. (2(k+1))!/(2k)!=(2k+2)(2k+1), isn't it? Just bear with me. The whole point of this exercise is which is larger, A or B?

7. Mar 3, 2013

### MP14

Yes my mistake, A = (2k+2)(2k+1) = (4k^2 + 6k + 2) and B = (4k^2 + 8k + 4), so B is larger.

8. Mar 3, 2013

### SammyS

Staff Emeritus
Yes it is.

Can you prove it ?

9. Mar 3, 2013

### MP14

Yes! Thank you!

(2(k+1))! = (2k+2)!
= (2k+2)(2k+1)!
= (2k+2)(2k+1)(2k)!
= (4k^2 + 6k + 2)(2k)!
< (4k^2 + 8k + 4)(2k)! < (4k^2 + 8k + 4)(2^(2k))(k!)^2 (based on assumption)
and the rest is algebra!
Thanks again!

10. Mar 4, 2013

### Dick

Sure. That's what I was getting at.