0
$\begingroup$

Prove that $\log(n!)\leq(\log(n))!$


My attempt:

I read somewhere that $n\leq\log(n!)\leq(\log(n))!$. But when I used calculator $\log(n!)$ can not be less than or equal to $(\log(n))!$.

Can you explain it in a formal way, please?

$\endgroup$
  • 2
    $\begingroup$ If you meant $\;\left(\log n\right)!\;$ then this number can only be taken via the Gamma Function, as it usually isn't a natural number. Did you mean this? Or perhaps there's a floor function there? $\endgroup$ – DonAntonio Jul 1 '16 at 9:22
  • $\begingroup$ Yes, $(\log(n))!$ $\endgroup$ – 1 0 Jul 1 '16 at 9:24
  • $\begingroup$ @Joanpemo I think it does not make great difference when $n$ is large. The bound is quite loose. $\endgroup$ – Brian Cheung Jul 1 '16 at 9:25
  • 1
    $\begingroup$ To be precise we should either write $\lfloor log(n) \rfloor !$ or $\Gamma(log(n) + 1)$ but I don't think it'll really matter. $\endgroup$ – Zubzub Jul 1 '16 at 9:28
  • 1
    $\begingroup$ I do think that the way to go here is en.wikipedia.org/wiki/Stirling%27s_approximation . Note that the first inequality is an immediate consequence $\endgroup$ – b00n heT Jul 1 '16 at 9:30
3
$\begingroup$

Let $x=\log(n)$

$\log(n!)<\log(n^n)=n\log(n)=xe^x$
$(\log(n))!=x!$

and the results follow by Factorial grows faster than Exponential.

$\endgroup$
  • 1
    $\begingroup$ Thanks for nice explanation. $\endgroup$ – 1 0 Jul 1 '16 at 9:41
4
$\begingroup$

As I suggested, using Strirling approximation is a very loose way, one immediately gets $$\log(n!)\approx n\log n$$ and $$\log(n)! \approx (\log(n))^{\log(n)}.$$ Cleraly the second dominates the first term, giving the claim.

$\endgroup$
  • $\begingroup$ Please, clear little bit this $$\log(n)! \sim (\log(n))^{\log(n)}.$$ $\endgroup$ – 1 0 Jul 1 '16 at 9:45
  • $\begingroup$ Just set $n=\log n$ in Stirling's formula $n! \sim \sqrt{2 \pi n}\left(\frac{n}{e}\right)^n$ and forget about the other terms $\endgroup$ – b00n heT Jul 1 '16 at 9:47
  • $\begingroup$ What is interesting (at least to me) is that $\log(x!) \gt \log(x)!$ holds if $x \gt 2.24836$. $\endgroup$ – Claude Leibovici Jul 1 '16 at 9:49
  • $\begingroup$ Wait... If what you claim is true, then this should contradict what I am saying... or would it? $\endgroup$ – b00n heT Jul 1 '16 at 9:50
  • $\begingroup$ @b00nheT I think you are correct. Put some numbers much larger to check it. This inequality describes asymptotic behavior so some small numbers may contradict the result. $\endgroup$ – Brian Cheung Jul 1 '16 at 9:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.