Solved

Proof by induction -- Inequalities

Posted on 2009-04-03
9
799 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
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
 
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
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
LVL 22

Accepted Solution

by:
NovaDenizen earned 250 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 250 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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
groupNoAdj 7 85
Calculating T-SCORE inside Excel. 3 115
Math Question: What is the max distance of x? 5 69
Turning python script into an applet 12 102
This is an explanation of a simple data model to help parse a JSON feed
Displaying an arrayList in a listView using the default adapter is rarely the best solution. To get full control of your display data, and to be able to refresh it after editing, requires the use of a custom adapter.
An introduction to basic programming syntax in Java by creating a simple program. Viewers can follow the tutorial as they create their first class in Java. Definitions and explanations about each element are given to help prepare viewers for future …
This is a video describing the growing solar energy use in Utah. This is a topic that greatly interests me and so I decided to produce a video about it.

912 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

Need Help in Real-Time?

Connect with top rated Experts

24 Experts available now in Live!

Get 1:1 Help Now