First Year Calculus Course Mathematical Induction Problem

MP14
Messages
5
Reaction score
0
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!
 
Physics news on Phys.org
MP14 said:
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!

But what factor does each side increase when you go from k to k+1?
 
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?
 
MP14 said:
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?

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?
 
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?
 
MP14 said:
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?

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?
 
Yes my mistake, A = (2k+2)(2k+1) = (4k^2 + 6k + 2) and B = (4k^2 + 8k + 4), so B is larger.
 
MP14 said:
Yes my mistake, A = (2k+2)(2k+1) = (4k^2 + 6k + 2) and B = (4k^2 + 8k + 4), so B is larger.
Yes it is.

Can you prove it ?
 
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
MP14 said:
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!

Sure. That's what I was getting at.
 
Back
Top