Fandom

巨大数研究 Wiki

コメント3

急増加関数 f 3(n) のテトレーションによる評価

Mikadukim 2016年6月22日 User blog:Mikadukim

急増加関数 \(f_3(n)\) をテトレーション関数 \(2\uparrow\uparrow n\) で上下から評価しました. (下からの評価はすでに知られているが, 上からの評価が知られているかわからなかったため.)

同様に \(f_m(n)\) を \(2\uparrow^{m-1} n\) で上下から評価することが期待されます.

主張

\begin{align*} 2\uparrow\uparrow (n+1) \le f_3(n) \le 2\uparrow\uparrow(2n) \quad(n\ge2). \end{align*}

ただし \(f_3(n)\) は急増加関数.

証明

\(f_3(n)\) は急増加関数の定義より,

\begin{align*} f_3(n) = f_2^n(n),\quad f_2(n) = 2^n n \end{align*} と計算できるのだった(寿司虚空編第6話 などを参照).

最初の不等号

最初の不等号 \(2\uparrow\uparrow (n+1) \le f_3(n)\) を帰納法で示そう. \(n=2\) のとき,

\begin{align*} f_3(2) = f_2^2(2) = 2^{2^2 \cdot 2} \cdot 2^{2} \cdot 2 \ge 2^{2^2} = 2 \uparrow \uparrow 3 \end{align*}

より不等号は成立.

\(n = k \ge 2 \)のとき不等号が成り立つと仮定する. \(n = k+1 \) のとき, 

\begin{align*} f_3(k+1) = f_2^{k+1}(k+1) = f_2(f_2^{k}(k+1)) = 2^{f_2^{k}(k+1)} f_2^{k}(k+1). \end{align*}

\(f_2\) は単調増加関数であるから,

\begin{align*} 2^{f_2^{k}(k+1)} f_2^{k}(k+1) \ge 2^{f_2^{k}(k)} f_2^{k}(k) = 2^{f_3(k)} f_3(k)\ge 2^{f_3(k)}. \end{align*}

帰納法の仮定より,

\begin{align*} 2^{f_3(k)} \ge 2^{2\uparrow \uparrow (k+1)} = 2\uparrow \uparrow (k+2). \end{align*}

よって \( f_3(k+1) \ge 2\uparrow \uparrow (k+2) \) であるから, \(n=k+1\)のときも不等号は成立する.

以上から, 数学的帰納法により全ての \(n\ge2\)に対して不等号が成り立つ. ■

2番目の不等号

2番目の不等号 \(f_3(n) \le 2\uparrow\uparrow(2n) \quad(n\ge2)\) を示そう.

\(n=2\) のとき, \begin{align*} f_3(2) &= 2^{2^2 \cdot 2} \cdot 2^{2} \cdot 2 = 2^{11} \le 2^{2^{2^2}} = 2\uparrow\uparrow 4 \end{align*} だから不等号は成立する.

\(n=3\) のとき, \begin{align*} f_3(3) &=f_2^3(3) =f_2(f_2^2(3)) \\&=2^{f_2^2(3)}f_2^2(3) \le 2^{f_2^2(3)} \cdot 2^{f_2^2(3)} \\&= 2^{f_2^2(3) \cdot 2} =2^{ 2^{2^3 \cdot 3} \cdot 2^3 \cdot 3 \cdot 2} \le 2^{2^{2^3 \cdot 3} \cdot 2^{7}} \\&= 2^{2^{31}} \le 2^{2^{2^5}} \le 2^{2^{2^{2^{2^2}}}} = 2\uparrow\uparrow 6 \end{align*} だから不等号は成立する.

よって \(n\ge4\) のときを示せばよい.

\( m\ge1, n\ge0 \) に対して, \(g(m,n) = 2 \uparrow \cdots \uparrow 2 \uparrow n \) (\(2\)が\(m\)個) とおく.

補題1

\begin{align*} g(m+1, n) g(m,n) \le g(m+1, n+1). \quad (m \ge1, n\ge0) \end{align*}

証明

たとえば \(m=2\) のとき, \( 2^{2^{2^n}} \cdot 2^{2^n} \le 2^{2^{2^{n+1}}} \) である. 簡単のためにこれを示そう(一般の\(m\)のときも同様).

\begin{align*}\text{(左辺)} &= 2^{2^{2^n} + 2^n} \le 2^{2^{2^n} + 2^{2^n}} \le 2^{2 \cdot 2^{2^n}} \\&= 2^{2^{2^n+1}} \le 2^{2^{2^{n}+2^n}} = 2^{2^{2 \cdot 2^{n}}} =\text{(右辺)}. ■ \end{align*}

補題2

\begin{align*} f_2^m(n) \le g(m+1, n+m-1) \quad (m \ge 0, n \ge 2). \end{align*}

証明

\(m\) に関する帰納法で示す. \(m=0\) のとき, 不等号は \(n \le 2^{n-1}\) となるので, これは成り立つ.

\(m=k \ge 0\) で不等号が成り立っていると仮定する. \(m=k+1\) のとき,

\begin{align*} f_2^{k+1}(n) = f_2(f_2^{k}(n)) = 2^{f_2^{k}(n)} f_2^{k}(n). \end{align*}

帰納法の仮定と \(g(m,n)\) の定義から,

\begin{align*} 2^{f_2^{k}(n)} f_2^{k}(n) &\le 2^{g(k+1, n+k-1)} g(k+1, n+k-1) \\&= g(k+2, n+k-1)g(k+1, n+k-1). \end{align*}

補題1より,

\begin{align*} g(k+2, n+k-1)g(k+1, n+k-1) \le g(k+2, n+k). \end{align*}

よって \(f_2^{k+1}(n)\le g(k+2, n+k)\) であるから, \(m=k+1\) のときも不等号は成り立つ.

以上から, 数学的帰納法により全ての \(m\ge0, n\ge2 \)に対して不等号が成り立つ. ■

証明の続き

補題2より, 特に \(m=n \ge2 \) のとき, \( f_3(n) \le g(n+1,2n-1)  \) が成り立つ.

\(n\ge 4\) のとき, \(2n-1 \le 2\uparrow\uparrow (n-1) \) であるので(かなり荒い評価!), \(g(m,n)\) の定義から

\begin{align*} f_3(n) &\le g(n+1,2n-1) \\&\le g(n+1, 2\uparrow\uparrow(n-1)) \\&= 2\uparrow\uparrow((n+1) + (n-1)) \\&= 2\uparrow\uparrow(2n) \end{align*}

だから不等号は成立する.

以上により, 主張が示された. ■

広告ブロッカーが検出されました。


広告収入で運営されている無料サイトWikiaでは、このたび広告ブロッカーをご利用の方向けの変更が加わりました。

広告ブロッカーが改変されている場合、Wikiaにアクセスしていただくことができなくなっています。カスタム広告ブロッカーを解除してご利用ください。

Fandomでも見てみる

おまかせWikia