ハイバー演算子とクヌースの矢印表記の関係

ハイバー演算子とクヌースの矢印表記の関係

(1)

\[ H_{0}\left(a,b\right)=b+1 \]

(2)

\[ H_{1}\left(a,b\right)=a+b \]

(3)

\[ H_{2}\left(a,b\right)=ab \]

(4)

\[ H_{3}\left(a,b\right)=a\uparrow b=a^{b} \]

(5)

\[ H_{4}\left(a,b\right)=a\uparrow\uparrow b=\underbrace{a^{a^{\cdot^{\cdot^{a}}}}}_{height\;b} \]

(6)負の整数に拡張

\[ H_{-n}\left(a,b\right)=H_{0}\left(a,b\right)\;,\;n=0,1,\cdots \]

(7)ハイバー演算子とクヌースの矢印表記の関係

\[ H_{n}\left(a,b\right)=a\uparrow^{n-2}b\;,\;n\in\mathbb{Z} \]

-

\(H_{n}\left(a,b\right)\)はハイパー演算子
\(a\uparrow^{n}b\)はクヌースの矢印表記

(1)

定義より明らかに\(H_{0}\left(a,b\right)=b+1\)となる。

(2)

定義より明らかに\(H_{1}\left(a,b\right)=a+b\)となる。

(2)-2

\begin{align*} H_{1}\left(a,b\right) & =a^{\left(1\right)}b\\ & =a^{\left(0\right)}a^{\left(1\right)}\left(b-1\right)\\ & =1+a^{\left(1\right)}\left(b-1\right)\\ & =1+\sum_{k=1}^{b-1}\left\{ a^{\left(1\right)}k-a^{\left(1\right)}\left(k-1\right)\right\} +a^{\left(1\right)}0\\ & =1+\sum_{k=1}^{b-1}1+a\\ & =1+\left(b-1\right)+a\\ & =a+b \end{align*}

(3)

\begin{align*} H_{2}\left(a,b\right) & =a^{\left(2\right)}b\\ & =a^{\left(1\right)}a^{\left(2\right)}\left(b-1\right)\\ & =a+a^{\left(2\right)}\left(b-1\right)\\ & =a+\sum_{k=1}^{b-1}\left\{ a^{\left(2\right)}k-a^{\left(2\right)}\left(k-1\right)\right\} +a^{\left(2\right)}\left(0\right)\\ & =a+a\sum_{k=1}^{b-1}1\\ & =a+a\left(b-1\right)\\ & =ab \end{align*}

(4)

\begin{align*} H_{3}\left(a,b\right) & =a^{\left(3\right)}b\\ & =a^{\left(2\right)}a^{\left(3\right)}\left(b-1\right)\\ & =a\left(a^{\left(3\right)}\left(b-1\right)\right)\\ & =a\left(a^{\left(3\right)}\left(0\right)\right)\prod_{k=1}^{b-1}\frac{a^{\left(3\right)}k}{a^{\left(3\right)}\left(k-1\right)}\\ & =a\left(a^{\left(3\right)}\left(0\right)\right)\prod_{k=1}^{b-1}a\\ & =a\left(a^{\left(3\right)}\left(0\right)\right)a^{b-1}\\ & =a^{b} \end{align*}

(5)

\begin{align*} H_{4}\left(a,b\right) & =a^{\left(4\right)}b\\ & =a^{\left(3\right)}a^{\left(3\right)}\cdots a^{\left(3\right)}a\\ & =a\uparrow a\uparrow\cdots\uparrow a\\ & =a\uparrow\uparrow b \end{align*}

(6)

\(n=0\)のとき定義より成り立つ。
\(n=k\)のとき成り立つと仮定すると、

\begin{align*} H_{0}\left(a,b\right) & =H_{-n}\left(a,b\right)\\ & =a^{-n}b\\ & =a^{-\left(n+1\right)}a^{-n}\left(b-1\right)\\ & =a^{-\left(n+1\right)}b\\ & =H_{-\left(n+1\right)}\left(a,b\right) \end{align*}

となり、\(n+k+1\)でも成り立つ。
故に

\[ H_{-n}\left(a,b\right)=H_{0}\left(a,b\right)\;,\;n=0,1,\cdots \]

(7)

\(n=2,3,\cdots\)のとき、

\(n=2\)のとき\(a^{\left(n\right)}b=ab\)なので成り立つ。

\(n=k\)のとき\(a^{\left(k\right)}b=a\uparrow^{k-2}b\)が成り立つと仮定すると、

\begin{align*} a^{\left(k+1\right)}b & =a^{\left(k\right)}a^{\left(k\right)}\cdots a^{\left(k\right)}a\\ & =a\uparrow^{k-2}a\uparrow^{k-2}a\cdots\uparrow^{k-2}a\\ & =a\uparrow^{k-1}a \end{align*}

となるので\(n=k+1\)のときも成り立つ。

故に数学的帰納法より

\[ H_{n}\left(a,b\right)=a\uparrow^{n-2}b\;,\;n=2,3,\cdots \]

が成り立つ。

\(n=1\)のとき、

\begin{align*} a\uparrow^{0}c & =a\uparrow^{-1}\left(a\uparrow^{0}\left(c-1\right)\right)\\ & =a\uparrow^{-1}\left(a\left(c-1\right)\right) \end{align*}

\(a\left(c-1\right)=b\)とおくと、\(c=1+\frac{b}{a}\)となるので、

\begin{align*} a\uparrow^{-1}b & =a\uparrow^{0}\left(1+\frac{b}{a}\right)\\ & =a\left(1+\frac{b}{a}\right)\\ & =a+b\\ & =H_{1}\left(a,b\right) \end{align*}

故に

\[ H_{1}\left(a,b\right)=a\uparrow^{-1}b \]

\(n=0,-1,\cdots\)のとき、

\begin{align*} a\uparrow^{-1}c & =a\uparrow^{-2}\left(a\uparrow^{-1}\left(c-1\right)\right)\\ & =a\uparrow^{-2}\left(a+c-1\right) \end{align*}

\(a+c-1=b\)とおくと、\(c=b-a+1\)となるので、

\begin{align*} a\uparrow^{-2}b & =a\uparrow^{-1}\left(b-a+1\right)\\ & =a+\left(b-a+1\right)\\ & =b+1\\ & =H_{0}\left(a,b\right) \end{align*}

となるので\(n=0\)で成り立つ。

\(n=k\)のとき、成り立つと仮定すると、

\begin{align*} H_{0}\left(a,b\right) & =a\uparrow^{k}b\\ & =a\uparrow^{k-1}a\uparrow^{k}\left(b-1\right)\\ & =a\uparrow^{k-1}b\\ & =H_{k-1}\left(a,b\right) \end{align*}

となるので、\(n=k-1\)でも成り立つ。

故に数学的帰納法より、

\[ H_{n}\left(a,b\right)=a\uparrow^{n-2}b\;,\;n=0,-1,\cdots \]

となる。

-

これらより、\(n=2,3,\cdots\)と\(n=1\)と\(n=0,-1,\cdots\)について成り立つので、

\[ H_{n}\left(a,b\right)=a\uparrow^{n-2}b\;,\;n\in\mathbb{Z} \]

となる。

ページ情報

タイトル

ハイバー演算子とクヌースの矢印表記の関係

URL

https://www.nomuramath.com/ob80k3tl/

SNSボタン