7
$\begingroup$

Of course, I can use Stirling's approximation, but for me it is quite interesting, that, if we define $k = (n-1)!$, then the left function will be $(nk)!$, and the right one will be $k! k^{n!}$. I don't think that it is a coincidence. It seems, that there should be smarter solution for this, other than Stirling's approximation.

  • 0
    I cannot explicitely explain why did I say so. Probably, I just wanted to point that it seems that there should be smarter solution others than Stirling's approximation. But, of course, I can be wrong.2012-10-09

2 Answers 2

3

For $(nk)!$ your factors are $1,2,3,\dots, k$ then $k+1, \dots, 2k,2k+1 \dots, k!$.

For $k! k^{n!}$ your factors are $1,2,3,\dots, k$ but then constant $k,\dots,k$.

So every factor of (nk)! is > or = to each factor of k!k^(n!)

  • 0
    But total numher of factors in the first function is $n!$, while in the second it is $k+n!$, so it has extra $k$ factors, each equals to $k$2012-10-10
0

Take $\log$ on both sides and use the $\log {n!} = \Theta(n\log n)$. The first terms becomes $\Theta(n!\log{(n!)})$, the second one becomes $\Theta((n-1)!\log {(n-1)!}) + \Theta(n!\log{(n-1)!})$. So it's obvious that the first terms grows faster than the second one.

  • 0
    That looks an awful lot like a proof that $n! log(n!)$ is $\Theta(n!(\log(n-1)!))$ to me (since $n! \log n$ grows more slowly than either of the other two terms). It looks to me like you need sharper asymptotics than $\Theta$-notation gives you, which leads back towards Stirling's approximation...2013-09-06