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)

```

```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search