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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/