Is n! Always Greater Than n^2? An Induction Proof

[ristin]

I have to do an induction proof that n!>n^2

 

[HallsofIvy]

You have a very fundamental problem here: n!> n^2 is NOT true for all positive integers. Please recheck the statement of the problem.

 

[ristin]

yes it is true when n>3, how do you prove it when n>3

 

[HallsofIvy]

Okay, that's a different problem. To use induction to prove that P(n) is true for all n\ge a you must prove two things:
1) That P(a) is true.
2) That if P(k) is true, for some integer k\ge a then P(k+1) is true.

Here, P(n) is "n!> n^2" for n\ge 4.
(1) So P(a)= P(4) is "4!> 4^2". 4!= 4(3)(2)(1)= 24 while 4^2= 16. Yes, 24> 16.

(2) Now assume that k!> 2^k for some k> 3. Then
(k+1)!= (k+1)(k!)> (k+1)2^k
Now we need to show that (k+1)(k^2)> (k+1)^2.

Since k+1> 0 we really only need to show that k^2> k+1. Let's do a separate induction to prove that n^2> n+ 1 for n> 1. If n= 2, 2^2= 4 while 2+ 1= 3. Yes, 4> 3.

Now assume that k^2> k+1 for some k. Then
(k+1)^2= k^2+ 2k+ 1> (k+1)+ 2k+ 1= 3k+ 2
= (k+1+ 1)+ 2k> (k+1+ 1).
That is, (k+1)^2> (k+1)+ 1 so the statement "n^2> n+1" is true for all n larger than 1.

Now that we know (k+1)k^2> (k+1)^2, it follows that (k+1)!> (k+1)k^2> (k+1)^2 and we are done.

 

[ristin]

yes i do know how to do them, this one is just stumping me, to how to prove it, i know my basis step is when n=4 and then we assume P(n) is true and prove that P(n+1) is also true. I multiplied both sides of my inequality by (n+1) to get n!(n+1)>n^2(n+1) which is equal to (n+1)!>n^2(n+1) then i got stuck

 

[ristin]

I need to prove n!>n^2 not 2^n i have done this proof before

 

[ristin]

do you see what i mean? that what you solved was n!>2^n where I need to solve n!>n^2?

 

[ristin]

on (2) when you went from (k+1)!= (k+1)(k!)> (k+1)2^k to (k+1)(k^2)> (k+1)^2 why did you get rid of the k!

 

[ristin]

how in (2) when you went from (k+1)!=(k+1)(k!)>(k+1)k^2 to (k+1)(k+2)>(k+1)^2

 

[ristin]

Thank you for all of your help! I figured it out :)