Proving n2 < n! for n > 3: Simplifying the Induction Step

In summary: So in summary, the proof by induction that n2 < n! for n > 3 seems to be a bit "forced" and there is no simpler way of doing it. The base case (n = 4) is obviously true and the induction step involves manipulating both sides of the inequality until we get to the desired result. This is a common issue with inequalities and it is not something to worry about too much. The proof presented is clear, clean, and well-reasoned.
  • #1
murshid_islam
457
19
i have to prove by induction that n2 < n! for n > 3

this is what i have done:

the base case (n = 4) is obviously true since 42 < 4!

now, assume that it is true for n = k, i.e., k2 < k!

now i have to prove it for n = k+1

since k > 3,
1 < k-1
1(k+1) < (k-1)(k+1)
k+1 < k2 - 1 < k2 < k!
k+1 < k!
(k+1)(k+1) < (k+1)k!
(k+1)2 < (k+1)!

what i have done seems ok to me. but is there any simpler way to do the induction step? what i have done seems a bit "forced" (if you know what i mean).

thanks in advance.
 
Mathematics news on Phys.org
  • #2
murshid_islam said:
i have to prove by induction that n2 < n! for n > 3

this is what i have done:

the base case (n = 4) is obviously true since 42 < 4!

now, assume that it is true for n = k, i.e., k2 < k!

now i have to prove it for n = k+1

since k > 3,
1 < k-1
1(k+1) < (k-1)(k+1)
k+1 < k2 - 1 < k2 < k!
k+1 < k!
(k+1)(k+1) < (k+1)k!
(k+1)2 < (k+1)!

what i have done seems ok to me. but is there any simpler way to do the induction step? what i have done seems a bit "forced" (if you know what i mean).

thanks in advance.
The steps you take seem correct. A bit simpler way is to think of what you want to prove: (k+1)2<(k+1)! and by using equivalent relations to simplify it, like this for example:

(k+1)2<(k+1)!<=>
(k+1)(k+1)<k! (k+1)<=> *note k+1>0*
k+1<k!

We know that k2<k! so we just have to prove that k+1<k2, which is easy because k(k-1)>1 for any k>3
 
Last edited:
  • #3
I'm not a big fan of this particular inductive proof, since I've never found a short argument that didn't require me to manipulate both sides of the inequality like that. I've seen a similar proof on www.inductiveproofs.com that is 2^n < n! -- maybe that one will provide some inspiration.
 
  • #4
murshid_islam said:
i have to prove by induction that n2 < n! for n > 3

this is what i have done:

the base case (n = 4) is obviously true since 42 < 4!

now, assume that it is true for n = k, i.e., k2 < k!

now i have to prove it for n = k+1

since k > 3,
1 < k-1
1(k+1) < (k-1)(k+1)
k+1 < k2 - 1 < k2 < k!
k+1 < k!
(k+1)(k+1) < (k+1)k!
(k+1)2 < (k+1)!

what i have done seems ok to me. but is there any simpler way to do the induction step? what i have done seems a bit "forced" (if you know what i mean).

thanks in advance.

Thereis no simpleway of doing this . For all mathematcialproof by inductionyou must assume p(k) is true and then prove p(K+1) is true for all n =1,2... which you haveseem tobe done any way
 
  • #5
murshid_islam said:
i have to prove by induction that n2 < n! for n > 3

this is what i have done:

the base case (n = 4) is obviously true since 42 < 4!

now, assume that it is true for n = k, i.e., k2 < k!

now i have to prove it for n = k+1

since k > 3,
1 < k-1
1(k+1) < (k-1)(k+1)
k+1 < k2 - 1 < k2 < k!
k+1 < k!
(k+1)(k+1) < (k+1)k!
(k+1)2 < (k+1)!

what i have done seems ok to me. but is there any simpler way to do the induction step? what i have done seems a bit "forced" (if you know what i mean).

thanks in advance.

i know exactly what you mean. the trouble is, for n < 4, the theorem simply isn't true:

12 = 1! = 1
22 > 2! = 2
32 > 3! = 6

and it's not like for n = 3, we have equality, or that 32 is "just barely" more than 3!, the break-even point is somewhere between 3 and 4 (if you were using the gamma function, for example). so when we get to the part where we use n > 3:

1 < k-1

it's not "elegant", we prove something a little stronger than we need (after all, k = 3 would make that statement true, but then our "base case" fails).

this often happens with inequalities, the bounding term is often something that is more than "just barely greater than".

i wouldn't worry over-much about this, your proof is clear, clean, and well-reasoned. there's bigger molehills to make into mountains, if you're into that sort of thing.
 

1. What is proof by induction?

Proof by induction is a mathematical technique used to prove that a statement is true for all natural numbers. It involves breaking down the statement into a base case and an inductive step, and then showing that if the statement is true for one natural number, it is also true for the next number.

2. When is proof by induction used?

Proof by induction is used when we want to prove that a statement is true for all natural numbers, but it is not practical or feasible to check each individual case. It is a powerful and efficient method for proving statements about infinite sets.

3. What are the steps for a proof by induction?

The typical steps for a proof by induction are: (1) establish a base case, usually by directly evaluating the statement for the smallest possible natural number; (2) assume that the statement is true for some arbitrary natural number, known as the inductive hypothesis; (3) use the inductive hypothesis to prove that the statement is also true for the next natural number; and (4) conclude that the statement is true for all natural numbers by the principle of mathematical induction.

4. Can proof by induction be used for all types of statements?

No, proof by induction can only be used for statements that involve natural numbers. It cannot be used for statements that involve real or complex numbers, for example.

5. Are there any common mistakes to watch out for in a proof by induction?

Yes, there are a few common mistakes that can occur in a proof by induction. These include incorrectly setting up the base case, making assumptions about the inductive step that are not supported by the inductive hypothesis, and using circular reasoning. It is important to carefully check each step of the proof and make sure it is logically sound.

Similar threads

Replies
13
Views
1K
  • General Math
Replies
8
Views
1K
Replies
5
Views
2K
Replies
4
Views
283
Replies
7
Views
3K
  • Calculus and Beyond Homework Help
Replies
15
Views
1K
  • General Math
Replies
3
Views
1K
  • General Math
Replies
10
Views
1K
  • General Math
Replies
7
Views
2K
Back
Top