Proving n! is Greater than n^2 and n^3: Induction Proof for Integers

[smithnya]

Homework Statement

Prove that n! > n² for every integer n ≥ 4, whereas n! > n³ for every integer n ≥ 6.

Homework Equations

See above.

The Attempt at a Solution

Ok, I am attempting an induction proof, but I seem to be stuck in the following step. In any case, I don't even know if what I have is correct. I'm skipping over n=1 and n=k.

for n = k+1
(k+1)! = k!(k+1)

k!(k+1) > (k+1)²

I don't know what to do next or even if I'm on the right path.

I think if I can get help with this first part I might be able to solve the second part (n! > n³).

 

[Hodgey8806]

Remember your proof is for n>=4, should you actually skip of "n=1" or should you have skipped over something else?

Also, remember that you ASSUME true for n=k. Which looks like this:
k!≥k²

Now, what should we do? Well you have checked it for k+1 as:

(k+1)!≥(k+1)²

Now, we have:(k+1)k! > (k+1)(k+1)

How can we get this left side to look an awful lot like our assumption for n=k?
What should we do with that k+1?
Lastly, what do we know about k+1 in relation to k^2 for integers 4 or larger?

 

[smithnya]

Ok, yeah, initially I should have used n= 4, I believe.

In the case of k!(k+1) = (k+1)(k+1) is it permitted to "factor" out an (k + 1) term, leaving us with k! > k+1? It would hold true for n≥ 4, right?

 

[dot.hack]

I'm an analysis student as well and I'm running around these boards answering proofs as best as I know how. I'm not sure if the last step in this proof is rigorous but i'll try anyways.
Starting from where you left off, divide both sides by (k+1)
this gives k! > k+1. We know that k! is certainly greater than k*(k-1) (as these terms are just part of k!) so if we can prove that k*(k-1) is larger than k+1 we've proved that k! is as well. So let's see. Let k*(k-1) be > k+1 . Divide both sides by k. this gives k-1 > 1+ 1/k or k> 2+1/k. This will absolutely be true for every k> 3 and thus every k greater than or equal to 4. I'm not sure if that last claim can be considered rigorous of not, but it will certainly be true. Anyways, hope that helps, and if anyone has suggestions for my proof let me have it.

 

[Hodgey8806]

Correct, it is permitted because we know that we are NOT even possibly dividing by a zero (anytime you "might" cancel out, you have to make sure a zero couldn't possibly be there.

This does hold true, but we want it to be more explicit. So instead of ending with this is true, we want to bring it back to the assumed relationship for n=k. So we have here that k!≥k², and we have k!>k+1. So if we can "line these up" properly, we'll see that the assumption shows that it is true for n=k.

Does that make sense?

 

[dot.hack]

Yea, absolutely. I'm just trying to get as much practice as I can so thank you for the advice.

 

[smithnya]

You mentioned in your previous post that we need to make our n = k+1 form resemble the original n!=n^2 form. Is that correct? Once we have k! > k+1, I really don't have an idea about how to do that.

 

[Hodgey8806]

That's ok. Let's not think of n's though. Let's think of k's. We want the k!>=k+1 to resemble our assumption that k!>=k^2. So if we know k^2>=k+1, what can we write using transitivity--it will look an awful lot like k!>=k^2

 

[dot.hack]

I'm a little confused because the original equation was an inequality (n! > n^2) not an equality (n! = n^2). Assuming you mean the original n! > n^2 it is just a matter of arranging the terms we already know and multiplying. We know that k! > k*(k-1) (by the definition of k!) and we showed that k*(k-1) > k+1. So we can arrange these as
k! > k*(k-1) > k+1 multiply through by k+1 and we get
k!*(k+1) > (k+1)*k*(k-1) > (k+1)*(k+1)
but this can be re-written as (k+1)! > (k+1)*k*(k-1) > (k+1)^2. Where the middle terms are just the first three terms of (k+1)!.
Make sense? / was that what you were asking?

 

[smithnya]

You are right dot.hack. I meant > not =. Thanks for your help.

Hodgey, the only think I can think of to bring the proof full circle is to reaffirm that (k +1)! > (k+1)². What am I missing?