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

[murshid_islam]

i have to prove by induction that n² < n! for n > 3

this is what i have done:

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

now, assume that it is true for n = k, i.e., k² < 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 < k² - 1 < k² < k!
k+1 < k!
(k+1)(k+1) < (k+1)k!
(k+1)² < (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.

 

[C0nfused]

i have to prove by induction that n² < n! for n > 3

this is what i have done:

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

now, assume that it is true for n = k, i.e., k² < 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 < k² - 1 < k² < k!
k+1 < k!
(k+1)(k+1) < (k+1)k!
(k+1)² < (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)²<(k+1)! and by using equivalent relations to simplify it, like this for example:

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

We know that k²<k! so we just have to prove that k+1<k², which is easy because k(k-1)>1 for any k>3

 

[bryanfoobar]

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.

 

[foreverdream]

i have to prove by induction that n² < n! for n > 3

this is what i have done:

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

now, assume that it is true for n = k, i.e., k² < 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 < k² - 1 < k² < k!
k+1 < k!
(k+1)(k+1) < (k+1)k!
(k+1)² < (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

 

[Deveno]

i have to prove by induction that n² < n! for n > 3

this is what i have done:

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

now, assume that it is true for n = k, i.e., k² < 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 < k² - 1 < k² < k!
k+1 < k!
(k+1)(k+1) < (k+1)k!
(k+1)² < (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:

1² = 1! = 1
2² > 2! = 2
3² > 3! = 6

and it's not like for n = 3, we have equality, or that 3² 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.