Technically Exists

Theorem μ\mu-0

The mu factorial has the same growth rate as the mixed factorial in terms of dominance over translations.

nμ! [=] n∗n\mu! \eqv n^*

Lemma μ\mu-0

(n−1)μ!>2⋅n(n - 1)\mu! > 2 \cdot n for all n∈N0,n≥4n \in \N_0, n \ge 4.

Proof

Base case:

(4−1)μ!=3μ!=(3↑(2⋅(1+0)))=9>8=2⋅4\begin{align*} (4 - 1)\mu! &= 3\mu! \\ &= (3 \uparrow (2 \cdot (1 + 0))) \\ &= 9 \\ &> 8 \\ &= 2 \cdot 4 \\ \end{align*}

Induction step for n≥4n \ge 4:

nμ!=n↑n−2((n−1)μ!)>n↑n−2(2⋅n)by the induction hypothesis>n+(2⋅n)>2+(2⋅n)=2⋅(n+1)\begin{align*} n\mu! &= n \uparrow^{n - 2} ((n - 1)\mu!) \\ &> n \uparrow^{n - 2} (2 \cdot n) &&\text{by the induction hypothesis} \\ &> n + (2 \cdot n) \\ &> 2 + (2 \cdot n) \\ &= 2 \cdot (n + 1) \\ \end{align*}

Lemma μ\mu-1

n↑n−2n>(n−1)∗n \uparrow^{n - 2} n > (n - 1)^* for all n∈N0,n≥2n \in \N_0, n \ge 2.

Proof

Base cases:

2↑2−22=2⋅2=4>1=1∗=(2−1)∗3↑3−23=3↑3=27>3=1+2=2∗=(3−1)∗4↑4−24=4↑↑4>9=(1+2)⋅3=3∗=(4−1)∗\begin{align*} 2 \uparrow^{2 - 2} 2 &= 2 \cdot 2 \\ &= 4 \\ &> 1 \\ &= 1^* \\ &= (2 - 1)^* \\ 3 \uparrow^{3 - 2} 3 &= 3 \uparrow 3 \\ &= 27 \\ &> 3 \\ &= 1 + 2 \\ &= 2^* \\ &= (3 - 1)^* \\ 4 \uparrow^{4 - 2} 4 &= 4 \uparrow\uparrow 4 \\ &> 9 \\ &= (1 + 2) \cdot 3 \\ &= 3^* \\ &= (4 - 1)^* \\ \end{align*}

Induction step for n≥4n \ge 4:

(n+1)↑n−1(n+1)=(n+1)↑n−2((n+1)↑n−1n)>(n+1)↑n−2(2↑n−1n)>n↑n−2(2↑n−1n)>n↑n−2(2⋅n)=n↑n−2(n+n)>(n↑n−2n)↑n−2nby the Knuth Arrow Theorem>(n↑n−2n)↑n−3n>(n−1)∗↑n−3nby the induction hypothesis=n∗\begin{align*} (n + 1) \uparrow^{n - 1} (n + 1) &= (n + 1) \uparrow^{n - 2} ((n + 1) \uparrow^{n - 1} n) \\ &> (n + 1) \uparrow^{n - 2} (2 \uparrow^{n - 1} n) \\ &> n \uparrow^{n - 2} (2 \uparrow^{n - 1} n) \\ &> n \uparrow^{n - 2} (2 \cdot n) \\ &= n \uparrow^{n - 2} (n + n) \\ &> (n \uparrow^{n - 2} n) \uparrow^{n - 2} n &&\text{by the Knuth Arrow Theorem} \\ &> (n \uparrow^{n - 2} n) \uparrow^{n - 3} n \\ &> (n - 1)^* \uparrow^{n - 3} n &&\text{by the induction hypothesis} \\ &= n^* \\ \end{align*}

Proposition μ\mu-0

nμ!>n∗n\mu! > n^* for all n∈N0,n≥4n \in \N_0, n \ge 4.

Proof

nμ!=n↑n−2((n−1)μ!)>n↑n−2(2⋅n)by Lemma μ-0=n↑n−2(n+n)>(n↑n−2n)↑n−2nby the Knuth Arrow Theorem>(n−1)∗↑n−2nby Lemma μ-1>(n−1)∗↑n−3n=n∗\begin{align*} n\mu! &= n \uparrow^{n - 2} ((n - 1)\mu!) \\ &> n \uparrow^{n - 2} (2 \cdot n) &&\text{by Lemma } \mu\text{-0} \\ &= n \uparrow^{n - 2} (n + n) \\ &> (n \uparrow^{n - 2} n) \uparrow^{n - 2} n &&\text{by the Knuth Arrow Theorem} \\ &> (n - 1)^* \uparrow^{n - 2} n &&\text{by Lemma } \mu\text{-1} \\ &> (n - 1)^* \uparrow^{n - 3} n \\ &= n^* \\ \end{align*}

Proposition μ\mu-1

nμ!<(n+2)∗n\mu! < (n + 2)^* for all n∈N0n \in \N_0.

Proof

Base case:

0μ!=0<3=1+2=2∗=(0+2)∗\begin{align*} 0\mu! &= 0 \\ &< 3 \\ &= 1 + 2 \\ &= 2^* \\ &= (0 + 2)^* \\ \end{align*}

Induction step:

(n+1)μ!=(n+1)↑n−1(nμ!)<(n+1)↑n−1(n+2)∗by the induction hypothesis<(n+2)∗↑n−1(n+2)∗=(n+2)∗↑n2<(n+2)∗↑n(n+3)=(n+3)∗\begin{align*} (n + 1)\mu! &= (n + 1) \uparrow^{n - 1} (n\mu!) \\ &< (n + 1) \uparrow^{n - 1} (n + 2)^* &&\text{by the induction hypothesis} \\ &< (n + 2)^* \uparrow^{n - 1} (n + 2)^* \\ &= (n + 2)^* \uparrow^n 2 \\ &< (n + 2)^* \uparrow^n (n + 3) \\ &= (n + 3)^* \\ \end{align*}

Proof of Theorem μ\mu-0

By Proposition μ\mu-0, it cannot be the case that nμ! [<] n∗n\mu! \gs n^*. By Proposition μ\mu-1, it cannot be the case that nμ! [>] n∗n\mu! \gf n^*. Therefore, nμ! [=] n∗n\mu! \eqv n^*.

Referenced results

Knuth Arrow Theorem: Theorem 3.1 in Knuth’s iterated powers