?
Solved

Proof by induction -- Inequalities

Posted on 2009-04-03
9
Medium Priority
?
819 Views
Last Modified: 2012-05-06
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
Comment
Question by:jeffiepoo
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
9 Comments
 
LVL 84

Expert Comment

by:ozo
ID: 24058772

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
 
LVL 84

Expert Comment

by:ozo
ID: 24058841
would it be any easier to prove that
(n-1)! > n^2 ?
0
 
LVL 6

Author Comment

by:jeffiepoo
ID: 24059363
I don't get what you're getting at
0
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 25

Expert Comment

by:InteractiveMind
ID: 24059442
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
 
LVL 22

Accepted Solution

by:
NovaDenizen earned 1000 total points
ID: 24061768
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
 
LVL 31

Expert Comment

by:GwynforWeb
ID: 24062376
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
 
LVL 31

Expert Comment

by:GwynforWeb
ID: 24065015
 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
 
LVL 31

Assisted Solution

by:GwynforWeb
GwynforWeb earned 1000 total points
ID: 24065816
...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

Need protection from advanced malware attacks?

Look no further than WatchGuard's Total Security Suite, providing defense in depth against today's most headlining attacks like Petya 2.0 and WannaCry. Keep your organization out of the news with protection from known and unknown threats.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This article provides a brief introduction to tissue engineering, the process by which organs can be grown artificially. It covers the problems with organ transplants, the tissue engineering process, and the current successes and problems of the tec…
What do responsible coders do? They don't take detrimental shortcuts. They do take reasonable security precautions, create important automation, implement sufficient logging, fix things they break, and care about users.
In this fourth video of the Xpdf series, we discuss and demonstrate the PDFinfo utility, which retrieves the contents of a PDF's Info Dictionary, as well as some other information, including the page count. We show how to isolate the page count in a…
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…
Suggested Courses

743 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question