Expert: Paul Klarreich - 3/16/2009

Question
I need to prove that k! > k^2.  I am able to complete the induction, but then I need to show that k^2 > k+1.  Maybe I did the induction wrong.  Thank you for any help!

Answer
Questioner:   Jen
Category:  Advanced Math
Private:  No
 
Subject:  Proof
Question:  I need to prove that k! > k^2.  I am able to complete the induction, but then I need to show that k^2 > k+1.  Maybe I did the induction wrong.  Thank you for any help!
...........................................

I like to use n for these things and use k inside the proof.  Before we start, you always have to have a base case, which is usually, BUT DOES NOT HAVE TO BE, n = 1.
Now, in fact,  

if n = 1, n! is not > n^2 ( 1! = 1, and 1^2 = 1)

if n = 2, n! is not > n^2 ( 2! = 2, and 2^2 = 4)

if n = 3, n! is not > n^2 ( 3! = 6, and 3^2 = 9)

if n = 4, n! IS FINALLY > n^2 ( 4! = 24, and 4^2 = 16)

OK, so your theorem should say:

For all n >=4,  n! > n^2

I assume you checked the base case already.  YOU MUST DO THIS IN EVERY PROOF.

Assume:  k! > k^2   << don't forget to use this somewhere.
Prove:  (k + 1)! > (k + 1)^2

Now to prove that  A > B, you could show that A - B > 0.  Let's try that.

(k + 1)! - (k + 1)^2 =

(k + 1)k! - (k + 1)^2    << definition of factorial

which is greater than

(k + 1)k^2 - (k + 1)^2   << by assumption.

= k^3 + k^2 - (k + 1)^2

= k^3 + k^2 - (k^2 + 2k + 1)

= k^3 - 2k - 1

Now can we prove that is nonnegative?

Remember that k >= 4,  so   k = 4 + p, for some p >= 0

(4 + p)^2 = 64 + 48p + 4p^2 + p^3

So

k^3 - 2k - 1

= (4 + p)^3 - 2(4 + p) - 1

= 64 + 48p + 4p^2 + p^3 - 8 - 2p - 1

= 55 + 46p + 4p^2 + p^3

And all of that is positive.

I think that does it.