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

In summary, Homework Equations states that for every integer n ≥ 4, n! > n2, whereas for every integer n ≥ 6, n! > n3. The Attempt at a Solution states that the induction proof is stuck in the following step, however, they are skipping over n=1 and n=k. They are attempting an induction proof for n=k+1, however, they are stuck. They claim that if they can get help with the first part of the proof (n! > n2), they might be able to solve the second part (n! > n3). They are also an analysis student and are answering proofs as best they know how. They are confused about the last step in
  • #1
smithnya
41
0

Homework Statement


Prove that n! > n2 for every integer n ≥ 4, whereas n! > n3 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)2

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! > n3).
 
Physics news on Phys.org
  • #2
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!≥k2

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

(k+1)!≥(k+1)2

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?
 
  • #3
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?
 
  • #4
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.
 
  • #5
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!≥k2, 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?
 
  • #6
Yea, absolutely. I'm just trying to get as much practice as I can so thank you for the advice.
 
  • #7
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.
 
  • #8
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
 
  • #9
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?
 
  • #10
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)2. What am I missing?
 

1. What is an induction proof?

An induction proof is a mathematical method used to prove that a property or statement is true for all natural numbers. It involves breaking the proof into smaller steps and showing that the statement is true for the first natural number, known as the base case, and then showing that if the statement is true for any given natural number, it must also be true for the next natural number, known as the induction step.

2. How is induction used to prove n > n^2?

To prove that n > n^2, we use mathematical induction to show that the statement is true for the base case, which is when n = 1. Then, we assume that the statement is true for any given natural number k, and use this assumption to prove that it is also true for the next natural number k+1. This completes the induction step and proves that the statement is true for all natural numbers.

3. What is the base case in an induction proof of n > n^2?

The base case in an induction proof of n > n^2 is when n = 1. This means that we need to show that 1 > 1^2, which is true since 1 > 1.

4. What is the induction step in an induction proof of n > n^2?

The induction step in an induction proof of n > n^2 involves assuming that the statement is true for any given natural number k, and then using this assumption to prove that it is also true for the next natural number k+1. This step completes the proof and shows that the statement is true for all natural numbers.

5. Why is an induction proof used for n > n^2?

An induction proof is used for n > n^2 because it provides a systematic and logical way to prove that a statement is true for all natural numbers. This is especially useful for statements that involve infinitely many numbers, such as n > n^2. Using mathematical induction helps to simplify the proof and make it easier to understand and verify.

Similar threads

  • Calculus and Beyond Homework Help
Replies
15
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
418
  • Calculus and Beyond Homework Help
Replies
30
Views
2K
  • Calculus and Beyond Homework Help
Replies
7
Views
2K
  • Calculus and Beyond Homework Help
Replies
6
Views
981
  • Calculus and Beyond Homework Help
Replies
4
Views
986
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
7
Views
338
  • Calculus and Beyond Homework Help
Replies
9
Views
865
Back
Top