関数の基礎再帰関数自然数、総和、アッカーマン関数(Ackermann Function)

学習環境

情報系のための離散数学 (猪股俊光 (著)、南野謙一 (著)、共立出版)の第6章(関数の基礎)、6.5(再帰関数)、問6.10、問6.11の解答を求めてみる。

問6.10

再帰関数の定義。

\begin{array}{l} n = 0 \\ s u m (n) = 0 \\ n \geq 1 \\ s u m (n) = s u m (n - 1) + n \end{array}

各値。

\begin{array}{l} s u m (0) = 0 \\ s u m (1) = s u m (0) + 1 = 0 + 1 = 1 \\ s u m (2) = s u m (1) + 2 = 3 \\ s u m (3) = s u m (2) + 3 = 6 \\ s u m (4) = s u m (3) + 4 = 10 \\ s u m (5) = s u m (4) + 5 = 15 \\ s u m (6) = s u m (5) + 6 = 21 \end{array}

問6.11

\begin{array}{l} A (0, 0) = 1 \\ A (0, 1) = 2 \\ A (1, 0) = A (1 - 1, 1) = A (0, 1) = 2 \\ A (1, 1) = A (0, A (1, 0)) = A (0, 2) = 3 \\ A (1, 2) = A (0, A (1, 1)) = A (0, 3) = 4 \end{array}