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 :)