Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

n Factorial - Prove Lower Bound is n^(n/2)


Date: 09/11/2001 at 01:27:02
From: Johnny Stevens
Subject: n Factorial - Prove lower bound is n^(n/2) 

Hi, Dr. Math,

I am trying to prove the following:

n^(n/2) <= n!

I tried using induction. With n = 1, the inequality holds. But I don't 
know how to proceed. I used (n+1)^(n/2), but couldn't find a way to 
show that it is <= (n+1)! or n!(n+1)

Thanks in advance.


Date: 09/14/2001 at 19:20:57
From: Doctor Floor
Subject: Re: n Factorial - Prove lower bound is n^(n/2) 

Hi, Johnny,

Thanks for writing.

Starting with n^(n/2) <= n! we can square both sides to get an 
equivalent equation

  n^n <= (n!)^2.

It is easy to check the correctness for n = 1,2,3,4.

Now we want to apply mathematical induction: Given n^n <= (n!)^2 (the 
induction hypothesis) we try to prove that (n+1)^(n+1) <= ((n+1)!)^2. 

Starting with ((n+1)!)^2 and applying the induction hypothesis we find

  ((n+1)!)^2 = (n!)^2 * (n+1)^2 >= n^n * (n+1)^2.

With this it remains to be proven that n^n * (n+1)^2 >= (n+1)^(n+1). 
To achieve this we note that the following equations are equivalent:

  n^n * (n+1)^2 >= (n+1)^(n+1)
  n^n >= (n+1)^(n-1)
  n >= ( (n+1)/n )^(n-1)
  ( (n+1)/n )^(n-1) <= n

To prove the final equation we try to find the x for which

  ( (n+1)/n )^x <= n.

This x is given by x = [base (n+1)/n]log(n). Since the function 
f(x)=( (n+1)/n )^x is an increasing function, it is enough to show 
that x >= n-1. In fact we will show that x>n (provided that n>=4).

To do this, we note

  x = [base (n+1)/n]log(n)

        [base n]log(n)
    = ----------------------
      [base n]log( (n+1)/n )

              1
    = ---------------------
      [base n]log(n+1) - 1

Now we will show that for n >= 4

   [base n]log(n+1) - 1 < 1/n    [*]

which proves that indeed x>n. For that we use that the derivative

   d                     1
   -- base[n]log(x) = --------
   dx                 x * ln(n)

and thus for n>e and thus indeed for n>=4:

     d                        1
  [  -- base[n]log(x) ]     < -
     dx                x=n    n

Also this derivative is a decreasing function. So we can conclude that 

  base[n]log(n+1) - base[n]log(n) < 1/n

which is exactly [*].

So indeed we have proved that the induction step n-->n+1 is valid for 
n >= 4. Since it was easy to check the initial values n = 1,2,3,4 this 
was exactly what was required.

If you need more help, just write back.

Best regards,
- Doctor Floor, The Math Forum
  http://mathforum.org/dr.math/   


Date: 09/14/2001 at 23:01:50
From: Doctor Jeremiah
Subject: Re: n Factorial - Prove lower bound is n^(n/2) 

Hi Johnny,

Here is how I would do it:

Assume:         n^(n/2) <= n!

Test:           n^(n/2) <= n!  <==  n=1
                1^(1/2) <= 1!
                      1 <= 1

Now try to show for n = n+1:

                n^(n/2) <= n!  <==  n=n+1
        (n+1)^((n+1)/2) <= (n+1)!
        (n+1)^(n/2+1/2) <= n!(n+1)
(n+1)^(n/2+1/2) / (n+1) <= n!(n+1) / (n+1)
    (n+1)^(n/2+1/2 - 1) <= n!
        (n+1)^(n/2-1/2) <= n!
        (n+1)^((n-1)/2) <= n!

Now this is where you got stuck. It's also where I got stuck. But then 
I realized that I don't have to show that (n+1)^((n-1)/2) is less than 
n! All I have to do is show that it's less than n^(n/2):

        (n+1)^((n-1)/2) <= n^(n/2) <= n!

If I can show that (n+1)^((n-1)/2) is less than n^(n/2), then I will 
have proved that it's less than n! because our premise is that 
n^(n/2) <= n!

        (n+1)^((n-1)/2) <= n^(n/2)

So what do you do with things that have exponents? You use logarithms.

        (n+1)^((n-1)/2) <= n^(n/2)
 log( (n+1)^((n-1)/2) ) <= log( n^(n/2) )
 ((n-1)/2) log( (n+1) ) <= (n/2) log( n )

Now we just move things around:

 ((n-1)/2) log( (n+1) ) <= (n/2) log( n )
 ((n-1)/2) log( (n+1) ) / log( n ) <= (n/2) log( n ) / log( n )
 ((n-1)/2) log( (n+1) ) / log( n ) <= (n/2)
 ((n-1)/2) log( (n+1) ) / log( n ) / ((n-1)/2) <= (n/2) / ((n-1)/2)
 log( (n+1) ) / log( n ) <= (n/2) / ((n-1)/2)
 log( (n+1) ) / log( n ) <= n/(n-1)
 log( (n+1) - n ) <= n/(n-1)
 log( 1 ) <= n/(n-1)
 0 <= n/(n-1)

Is this true for all n greater than one? (We don't need to prove it 
for n = 1 because we already used that as our test case to start the 
proof off.)

For n = 2,3,4,5 (or for any positive number) there is no way that 
n/(n-1) could be less than zero, so we have proved that 
(n+1)^((n-1)/2) <= n^(n/2) for all n greater than one, and since we 
had a premise that n^(n/2) <= n! we have also proved that 
(n+1)^((n-1)/2) <= n! for all n greater than one. And since we showed 
that n^(n/2) <= n! was true for n = 1 in our test case,  n^(n/2) <= n! 
for any n greater than 0.

But what about n = 0? There is no way to show it for n-0 because 
n^(n/2) is indeterminate at 0, our test case was n = 1, and our proof 
showed for n>1 (we added 1 to n; we didn't subtract so we didn't prove 
it for anything lower than n = 2).

- Doctor Jeremiah, The Math Forum
  http://mathforum.org/dr.math/   
    
Associated Topics:
High School Exponents
High School Logs
High School Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/