2

Which function grows faster: $(n!)!$ or $((n-1)!)!\ (n-1)!^{n!}?$ [Show using logarithms.]

This is exercise 2(c) from chapter 9 of Concrete Mathematics (Knuth, Patashnik, Graham). A few computer calculations and one can see that the former grows much faster, and the answer section suggests using logarithms to show that it does indeed.

The farthest I have gone with this question is $\ln(((n-1)!)!\ (n-1)!^{n!}) \asymp \ln((n-1)!^{n!})$. Now, if I can show $\ln((n-1)!^{n!})\prec\ln((n!)!),$ the conclusion will follow.

Marwan Mizuri
  • 182

1 Answers1

3

$$ \frac{(n!)!}{((n-1)!)!(n-1)!^{n!}}=\frac{\prod_{k=(n-1)!+1}^{n!}k}{(n-1)!^{n!}}$$ There are $n!$ factors $(n-1)!$ in the denominator. At the same time, tere are "only" $n!-(n-1)!=(n-1)\cdot (n-1)!$ factors in the numerator, but each is $>(n-1)!$. Note however, that $(n-2)\cdot (n-1)!$ of these factors are $>2(n-2)!$, that $(n-3)\cdot (n-1)!$ of these factors are $>3(n-2)!$, and so on. We conclude that $$\begin{align}\prod_{k=(n-1)!+1}^{n!}k& =\prod_{j=1}^{n-1}\;\prod_{k=j(n-1)!+1}^{(j+1)(n-1)!}k\\ &>\prod_{j=1}^{n-1}(j(n-1)!)^{(n-1)!}\\ &=(n-1)!^{(n-1)(n-1)!}\cdot \prod_{j=1}^{n-1}j^{(n-1)!}\\ &=(n-1)!^{(n-1)\cdot(n-1)!}\cdot(n-1)!^{(n-1)!}\\&=(n-1)!^{n!}\end{align}$$ We get a stronger result by noting that half of the $(n-1)!$ factors that we estimated merely as $>(n-1)!$ are in fact $>\frac32(n-1)!$. This makes the estimate grow by a factor of $(\frac32)^{(n-1)!/2}$ and we ulitmately obtain $$ \frac{(n!)!}{((n-1)!)!(n-1)!^{n!}}>\left(\frac32\right)^{(n-1)!/2}\to\infty$$

Hagen von Eitzen
  • 374,180