Proof by induction -- Inequalities

Posted on 2009-04-03
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)
Question by:jeffiepoo
LVL 84

Expert Comment

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

Expert Comment

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

Author Comment

ID: 24059363
I don't get what you're getting at
Migrating Your Company's PCs

To keep pace with competitors, businesses must keep employees productive, and that means providing them with the latest technology. This document provides the tips and tricks you need to help you migrate an outdated PC fleet to new desktops, laptops, and tablets.

LVL 25

Expert Comment

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..
LVL 22

Accepted Solution

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.
LVL 31

Expert Comment

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.
LVL 31

Expert Comment

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.
LVL 31

Assisted Solution

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.

Featured Post

Netscaler Common Configuration How To guides

If you use NetScaler you will want to see these guides. The NetScaler How To Guides show administrators how to get NetScaler up and configured by providing instructions for common scenarios and some not so common ones.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
hardness of water, iron in it, and effect on humans.. 6 73
Does a rhombus have 2 pairs of parallel sides 5 64
iSeries email authority 6 57
This article will show, step by step, how to integrate R code into a R Sweave document
If you’re thinking to yourself “That description sounds a lot like two people doing the work that one could accomplish,” you’re not alone.
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …

777 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