この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

計算理論・ラムダ計算の問題

難易度 2大学院の講義の演習問題レベル証明問題大学院数学計算理論・ラムダ計算

この問題では $N = {0, 1, 2, \dots}$ （ $0$ を含む）とする。関数 $A : N \times N \to N$ を次の再帰式で定める（アッカーマン・ペーター関数）。
$A (0, n) = n + 1, A (m + 1, 0) = A (m, 1), A (m + 1, n + 1) = A (m, A (m + 1, n)) (m, n \in N) .$
この再帰式によって $A$ がすべての $(m, n) \in N \times N$ で一意に定まる全域関数であることは用いてよい。

すべての $n \in N$ に対して
$A (3, n) = 2^{n + 3} - 3$
が成り立つことを証明せよ。

この問題で使うもの

アッカーマン関数の値（説明と入口の問題）
数学的帰納法と一般項の推定（説明と入口の問題）

この問題を解けるようになるまで（16 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

$m$ を小さい順に固定して考え、 $A (1, n)$ , $A (2, n)$ , $A (3, n)$ の式を、それぞれ $n$ に関する帰納法で順に求めるとよい。

ヒント 2

第 3 式から $A (m + 1, n + 1) = A (m, A (m + 1, n))$ なので、 $A (m, \cdot)$ の閉じた式が分かっていれば $A (m + 1, n)$ についての漸化式が得られる。例えば $A (1, n + 1) = A (1, n) + 1$ となる。

ヒント 3

$A (1, n) = n + 2$ 、 $A (2, n) = 2 n + 3$ をまず示すと、 $A (3, n + 1) = A (2, A (3, n)) = 2 A (3, n) + 3$ 、 $A (3, 0) = A (2, 1) = 5$ が得られる。あとはこの漸化式に対して帰納法を使う。

採点の観点と模範解答

自分で証明を書いてから、採点の観点で見比べてください。

採点の観点を見る

$A (1, 0) = A (0, 1) = 2$ と $A (1, n + 1) = A (0, A (1, n)) = A (1, n) + 1$ から、帰納法で $A (1, n) = n + 2$ を示している（2 点）
$A (2, 0) = A (1, 1) = 3$ と、 $A (1, k) = k + 2$ を $k = A (2, n)$ に適用した $A (2, n + 1) = A (2, n) + 2$ から、帰納法で $A (2, n) = 2 n + 3$ を示している（3 点）
本題の基底として $A (3, 0) = A (2, 1) = 5 = 2^{3} - 3$ を、定義の第 2 式と $A (2, n)$ の式から確かめている（2 点）
$A (3, n + 1) = A (2, A (3, n)) = 2 A (3, n) + 3$ を導き、帰納法の仮定を代入して $2^{n + 4} - 3$ になることを計算し、結論を述べている（3 点）

結果を記録する（このブラウザにだけ保存されます）:

模範解答を読む

$n$ に関する数学的帰納法を 3 回用いる。まず補題として $A (1, n)$ , $A (2, n)$ の閉じた式を示し、それを使って $A (3, n)$ の式を示す。

補題 1. すべての $n \in N$ に対して $A (1, n) = n + 2$ である。

証明（ $n$ に関する帰納法）。
- $n = 0$ のとき: 第 2 式（ $m = 0$ ）より $A (1, 0) = A (0, 1)$ であり、第 1 式より $A (0, 1) = 1 + 1 = 2 = 0 + 2$ 。
- $A (1, n) = n + 2$ を仮定して $A (1, n + 1) = n + 3$ を示す。第 3 式（ $m = 0$ ）より $A (1, n + 1) = A (0, A (1, n))$ 。第 1 式より $A (0, k) = k + 1$ なので $A (1, n + 1) = A (1, n) + 1$ 。帰納法の仮定より $A (1, n + 1) = (n + 2) + 1 = (n + 1) + 2$ 。

よって補題 1 が成り立つ。

補題 2. すべての $n \in N$ に対して $A (2, n) = 2 n + 3$ である。

証明（ $n$ に関する帰納法）。
- $n = 0$ のとき: 第 2 式（ $m = 1$ ）より $A (2, 0) = A (1, 1)$ 。補題 1 より $A (1, 1) = 1 + 2 = 3 = 2 \cdot 0 + 3$ 。
- $A (2, n) = 2 n + 3$ を仮定する。第 3 式（ $m = 1$ ）より $A (2, n + 1) = A (1, A (2, n))$ 。補題 1 を $k = A (2, n) \in N$ に適用すると $A (1, k) = k + 2$ なので、 $A (2, n + 1) = A (2, n) + 2$ 。帰納法の仮定より $A (2, n + 1) = (2 n + 3) + 2 = 2 (n + 1) + 3$ 。

よって補題 2 が成り立つ。

本題. すべての $n \in N$ に対して $A (3, n) = 2^{n + 3} - 3$ であることを $n$ に関する帰納法で示す。
- $n = 0$ のとき: 第 2 式（ $m = 2$ ）より $A (3, 0) = A (2, 1)$ 。補題 2 より $A (2, 1) = 2 \cdot 1 + 3 = 5$ 。一方 $2^{0 + 3} - 3 = 8 - 3 = 5$ なので成り立つ。
- $A (3, n) = 2^{n + 3} - 3$ を仮定して、 $A (3, n + 1) = 2^{n + 4} - 3$ を示す。第 3 式（ $m = 2$ ）より
$A (3, n + 1) = A (2, A (3, n)) .$
$A (3, n) \in N$ なので補題 2 を $k = A (3, n)$ に適用でき、 $A (2, k) = 2 k + 3$ 。したがって
$A (3, n + 1) = 2 A (3, n) + 3.$
帰納法の仮定を代入すると
$A (3, n + 1) = 2 (2^{n + 3} - 3) + 3 = 2^{n + 4} - 6 + 3 = 2^{(n + 1) + 3} - 3.$
よって $n + 1$ のときも成り立つ。

以上より、数学的帰納法によって、すべての $n \in N$ に対して $A (3, n) = 2^{n + 3} - 3$ が成り立つ。

計算理論・ラムダ計算の問題

この問題で使うもの

ヒント

採点の観点と模範解答

次のおすすめ

この問題の確認

間違いを報告する

関連する問題