• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 844
  • Last Modified:

Proof by induction -- Inequalities

Ok I can't figure out how to inductively prove the following inequalities, I have the base case and inductive hypothesis, I just don't see how to prove this stuff. I've already turned in the assignment, I'm just curious cause they never tell us. At least there's points in it for you guys.

1.) Prove that n! > n^3 when n is large enough. (n has to be greater than or equal to 6)

2.) Prove that n! < n^n for all positive integers by induction.

I just can't seem to prove these inequalities for P(K+1). Any help would be appreciated.

-Jeff   P.S. (If you solve one I'll give you half the points, unless only one is ever solved than I'll give you them all! HAHAHA)
0
jeffiepoo
Asked:
jeffiepoo
2 Solutions
 
ozoCommented:

Assuming that k! < k^k, what can you then say about (k+1)! and (k+1)^(k+1) ?

what do you know about 1! and 1^1
0
 
ozoCommented:
would it be any easier to prove that
(n-1)! > n^2 ?
0
 
jeffiepooAuthor Commented:
I don't get what you're getting at
0
What Security Threats Are We Predicting for 2018?

Cryptocurrency, IoT botnets, MFA, and more! Hackers are already planning their next big attacks for 2018. Learn what you might face, and how to defend against it with our 2018 security predictions.

 
InteractiveMindCommented:
You first assume that k!<k^k.
Now consider (k+1)! = (k+1)k! < (k+1)k^k,
it's easy to show that (k+1)^(k+1) > (k+1)k^k, in which case you're done.

As for (n-1)! > n^2, note that this is equivalent to n!>n^3. However, you may find it easier to prove that instead..
0
 
NovaDenizenCommented:
1.  n! > n^3 for all n >= 6.

First prove P(6), which is 6! > 6^3.  This is just easy arithmetic.

Then you have to prove P(k+1) given P(k) and k >= 6.
Given k! > k^3, and k >= 6, prove that (k+1)! > (k+1)^3.

Have you gotten this far?  The first thing you should do is expand the factorial and the polynomial.

2.  n! < n^n for all n >= 1.
This is actually not true.  1! < 1^1 reduces to 1 < 1, which is false.
Maybe you meant n! <= n^n for all n >= 0, or maybe n! < n^n for all n >= 2.
0
 
GwynforWebCommented:
n^n > n!

Assume true for n

(n+1)^(n+1) =  (n+1)(n+1)^n > (n+1)n^n

                 >  (n+1)n!   ( by inductive assumption)

                 =  (n+1)!

Hence if true for n true for n+1

Clearly true for n=2.  Hence by the principle of induction true for all n.
0
 
GwynforWebCommented:
 n^3  <  n!     (for n > 5)

Assume true for n

(n+1)^3 = n^3 + 3n^2 + 3n + 1
 
             <  n!  + 3n^2 + 3n + 1     (by inductive assumption)

             <  n!  + n^3 + n^3 +n^3    (if n > 3)

             <   n!  + n! + n! + n!        (by inductive assumption)

             <  4n!

             <  (n+1)n!  =  (n+1)!        (if n >4)
               
Hence if true for n true for n+1.

Since true for n=6 by the principle of induction true for all n.
0
 
GwynforWebCommented:
...a bit tidier is

(n+1)^3 = n^3 + 3n^2 + 3n + 1
 
             <  n^3 + n^3 + n^3 + n^3 = 4n^3     (if n > 3)

             <  4n!    (by inductive assumption)

             <  (n+1)n!  =  (n+1)!        (if n >4)  

 Hence if true for n true for n+1.
0

Featured Post

Hire Technology Freelancers with Gigs

Work with freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely, and get projects done right.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now