7
$\begingroup$

The asymptotic growth of the factorial function $n!$ is famously given by Stirling's formula as

$$n! \sim \sqrt{2 \pi n}\left(\frac{n}{e}\right)^n$$

Is there a similar formula for the iterated factorial

$$n\underbrace{!!\dots !}_n$$

perhaps in terms of tetration ${^{n}n}$ ?

The function grows fast to say the least, with the first terms being

$$ \begin{align} 1! &= 1 \\ (2!)! &= 2 \\ ((3!)!)! &\approx 2.6\times 10^{1746} \end{align} $$

and all following terms too large even for scientific notation.

$\endgroup$
  • $\begingroup$ Note, by the way, that this doesn't even come close to the growth rates of some functions over $\mathbb N$ that we know. $\endgroup$ – Akiva Weinberger Mar 10 '15 at 16:24
  • 1
    $\begingroup$ Plug $n!$ into $\sqrt{2\pi n}(n/e)^n$ to get $(n!)!$ (note that $n!!$ denotes the double factorial, because combinatorics hate us), repeat ad nauseam. $\endgroup$ – Najib Idrissi Mar 10 '15 at 16:26
  • $\begingroup$ @NajibIdrissi: Sure, but then it's not a closed form like Stirling's is anymore. $\endgroup$ – user139000 Mar 10 '15 at 16:27
  • 1
    $\begingroup$ Uh... I'm going to leave my comment above, but it's actually garbage! You really shouldn't listen to it. It's not at all true that you can compose equivalences like I suggested... Sorry for this lapse in judgement. For example $n \sim n+1$ but $e^n \not\sim e^{n+1}$... $\endgroup$ – Najib Idrissi Mar 10 '15 at 16:29
  • $\begingroup$ I mean, you learn something about the iterated factorial, it's just less than you might have hoped (it's a bit weaker than knowing it up to a multiplicative constant). $\endgroup$ – Qiaochu Yuan Mar 10 '15 at 16:39
4
$\begingroup$

Let $_k n$ denote $n!!\cdots !$ with $k$ factorials.

We will show that, given $n \ge 3$ and $k \ge 1$, $_k n$ lies between $^kn$ and $^{k+1} n$.

The key inequalities that we will make use of are

$(n/e)^n < n! < n^{n-1}$ for $n \ge 3$.

The left inequality follows from a Riemann Sum argument. The right inequality is obvious from $n * (n-1) \cdots * 2 < n * n \cdots n$.

Part I: Given $n \ge 3$, $_k n > \ ^kn$

Proof by induction:

Clearly true for $k=1$.

For $k=2$, $_2 n = n!! \ge (2n)! > n^n = \ ^2n$.

Now, assume $_k n > \ ^kn$ for some $k \ge 2$. Then

$_{k+1} n = (_k n)! > (^k n)! > (\frac{^k n}{e})^{^k n} > n^{^k n} = \ ^{k+1}n$.

Part II: Given $n \ge 3$, $_k n < {^{k+1} n}$.

We will prove the following lemma:

Lemma: Given $n \ge 3$, $_k n < \frac{^{k+1} n}{^k n}$

Proof by induction:

For $k=1$, we have $_1 n = n! < n^{n-1} = \frac{^2 n}{^1 n}$.

Given $_k n < \frac{^{k+1} n}{^kn}$, we have

$_{k+1} n = (_k n)! < (\frac{^{k+1} n}{^kn})! < (\frac{^{k+1} n}{^kn})^{\frac{^{k+1} n}{^kn}} = \frac{(^{k+1} n)^{\frac{^{k+1} n}{^k n}}}{(^{k} n)^{\frac{^{k+1} n}{^k n}}} < \frac{(n^{^k n})^{\frac{^{k+1} n}{^k n}}}{n^{\frac{^{k+1} n}{^k n}}} < \frac{n ^{^{k+1} n}}{n^{^k n}} = \ \frac{^{k+2} n}{^{k+1} n}$.

Therefore:

For $n \ge 3$ and $k \ge 1$, $^k n < _k n < {^{k+1} n}$.

$\endgroup$

Your Answer

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