   was wondering if this equation is true
  hi.. I believe that this equation is wrong:0 <= anlgn <= lg(n!) <= bnlgn ( a and b constant positive integers )am i right?   
  if a < b, n = 5a = 4, b = 820*lg(8) <= lg(8!) <= 40*lg(8)get a calculator! [smile]   ;  Hypothesis: 0 <= a*n*log(n) <= lg(n!) <= b*n*log(n) where a, b are positive integers.0 <= a*n*log(n) <= lg(n!) <= b*n*log(n) ==> a*n*log(n) <= b*n*log(n)Let's divide each side of the inequation by n*log(n).  This leaves us witha <= b where a, b are arbitrary positive integers.  Let a = 2, b = 1.a <= b is false.  Therefore, the hypothesis is false.Something's telling me that either:A) You didn't state the problemB) I didn't understand it correctly.   ;  thanks for the replies guys!yes i didn't state the problem correctly. I should have said that a < b@Alpha_ProgDes, 20*lg(8) <= lg(8!) is wrong, and 20*lg(5) <= lg(5!) is wrong too :(   ;Quote:Original post by valla2hi.. I believe that this equation is wrong:0 <= anlgn <= lg(n!) <= bnlgn ( a and b constant positive integers )am i right?This is almost (but not quite; see next paragraph) equivalent to saying that lg(n!) is Θ(n lg n). There is a well-known approximation for ln(n!) based on Stirling's approximation that is given by ln(n!) ~= n * ln(n) - n + (ln(n) + ln(2π))/2. In other words, n * log(n) is O(log(n!)) and Θ(log(n!)).However, with the constraint that a and b must be constant positive integers (rather than just constants), things are a little more messy. There is no such (a, b) that will satisfy the equation. Are you sure you didn't mean constant positive numbers?   ;  I think it is originally something like "there exist a and b so inequalities that is similar to what have been posted is true, and some other inequalities OP forgot to mention (like a<b) is true too".Otherwise, as it is stated by OP, it simply doesn't make sense whatsoever.Just for example,a=1,n=2, b=31*2*lg(2) <= log(2!) is of course false. No need to have calculator, try many numbers in search for counterexamples, nothing. Just smallest bit of thinking what numbers make it false.So either OP came to this 'hypothesis' himself (why, if he believes it is false), or misinterpreted something from somewhere.edit: maybe he actually want to prove that it is always false?For example i know that(for n>1)n!<nnsolog(n!)<log(n)*nso we now have that there is no a>=1, b>=1, n>1 so a*n*log(n)<=log(n!) is true. Lol.[Edited by - Dmytry on December 17, 2005 5:15:33 AM];  oh.. yes that was the problem! Thank you kSquared, you are right, a and b should be REAL number constants, not integers.. So the equation stands correct if a < 1.As for Stirling's approximation, i know it as:n! = sqrt(2*pi*n)*[(n/e)^n]*( 1 + Th(1/n) ) Can you tell me if i am right in the way to prove thatlg(n!) = Th( nlgn )?This is how i would do it:lg(n!) = lg [ sqrt(2*pi*n)*[(n/e)^n]*( 1 + Th(1/n) )  ]=> lg(n!) = lg[sqrt(2*pi*n)] + lg[(n/e)^n] + lg( 1 + Th(1/n) ) => lg(n!) = lg[sqrt(2*pi)] + 1/2lgn + nlg(n/e) + lg( 1 + Th(1/n) )=> lg(n!) = Th( nlg(n/e) ) = Th( n( lgn - lge ) )=> lg(n!) = Th(nlgn)To do so i ignored lower-order terms. Is it right?As for satisfing my original equation with (a, b), how should i go about finding the largest value of a ( which is < 1 )?Thanks, i really appreciate your helpedit: @Dmytry, yes a and b are reals with a < b...   ;  ok, makes sense now. As about finding largest value of a so a*n*lg(n)<lg(n!), let's first try to find in what range a should be.Firstly, if it must work for n=2 we need to havea*2*lg(2)<=lg(2)So, a can not be larger than 0.5 or it is false.Quick test with calculator shows that 0.5 works for larger n too, so we know that largest a is 0.5 and you may only need to prove it works for all n (edit: i mean all n>2 but it happens that it'll also work for all n)Hint for proof:log(n!)=log(1)+log(2)+log(3)...+log(n)(you can try grouping terms on the right, as in (log(1)+log(n)) + (log(2)+log(n-1)) , and prove that each is bigger than log(n) , so you'll have proof for even n, and then can prove it for odd n)Or try proving that if it is true for n , it is true for n+1 I can make proof if you have problems.[Edited by - Dmytry on December 17, 2005 7:48:13 AM];Quote:Original post by Dmytry... Quick test with calculator shows that 0.5 works for larger n too, so we know that largest a is 0.5 and you may only need to prove it works for all nProof that f(n) is Θ(g(n)) does not require that a*g(n) <= f(n) <= b*g(n) for all n, only that there exists an n0 such that for all n > n0 it is always true.   ;Quote:Original post by kSquaredQuote:Original post by Dmytry... Quick test with calculator shows that 0.5 works for larger n too, so we know that largest a is 0.5 and you may only need to prove it works for all nProof that f(n) is Θ(g(n)) does not require that a*g(n) <= f(n) <= b*g(n) for all n, only that there exists an n0 such that for all n > n0 it is always true.Yep, I should have said for all n>2 (choosing n0=2 just because it's handier than n0=42 or something.) He asked about finding largest a. [sidenote: Of course for say n>=10 , largest a is bigger than 0.5 , in fact largest a=log(n0!)/(n0*log(n0)) , if we need equation, err, inequality to work for n>=n0]I don't know why he need this largest a , because for proof that f(n) is Θ(g(n)) he can just have say a=0.25 or any other number that is easier to use in proof.[Edited by - Dmytry on December 17, 2005 11:37:01 AM]