Proof by induction: help

  • #1
410
12
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.
 

Answers and Replies

  • #2
139
0
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
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
Deveno
Science Advisor
906
6
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.
 

Related Threads on Proof by induction: help

  • Last Post
Replies
8
Views
5K
  • Last Post
Replies
9
Views
3K
  • Last Post
Replies
6
Views
3K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
6
Views
5K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
1
Views
3K
Replies
4
Views
2K
Replies
2
Views
7K
Top