グッドスタイン列
ここではグッドスタイン列 (Goodstein sequense) と呼ばれる数列を定義します.
やはり具体例で見ていきましょう. ここで初期値を 5 とします. g_1 := 5. そしてこれを遺伝的 2 進表記で表します.
g_1 = 5 = 2^2 + 1.
この表記の 2 を全て 3 に置き換えて -1 したものが次の項 g_2 となります.
g_1 = 2^2 + 1 → (3^3 + 1) - 1 = 3^3 = g_2.
ここで g_2 = 3^3 が遺伝的 3 進表記になっていることを確認してください. 次の項は先と同様に, この表記の 3 を全て 4 に置き換えて -1 したものです.
g_2 = 3^3 → (4^4) - 1 = g_3.
このままでは a_3 = 4^4 - 1 (= 255) は遺伝的 4 進表記ではありません. これを遺伝的 4 進表記に直すと, "繰り下がり" が起きて 4^4 が崩されます.
g_3 = 4^4 - 1 = (4^3)×3 + (4^2)×3 + 4×3 + 3.
a_4 はこの遺伝的 4 進表記に現れる 4 を全て 5 に置き換えて -1 したものです.
g_3 = (4^3)×3 + (4^2)×3 + 4×3 + 3
→ ((5^3)×3 + (5^2)×3 + 5×3 + 3) -1 = (5^3)×3 + (5^2)×3 + 5×3 + 2 = g_4.
大体どのようなものか判ったと思います. g_1 から g_7 までを書き下せば,
g_1 = 2^2 + 1 = 5
g_2 = 3^3 = 27
g_3 = 4^4 - 1 = (4^3)×3 + (4^2)×3 + 4×3 + 3 = 255
g_4 = (5^3)×3 + (5^2)×3 + 5×3 + 2 = 467
g_5 = (6^3)×3 + (6^2)×3 + 6×3 + 1 = 775
g_6 = (7^3)×3 + (7^2)×3 + 7×3 = 1197
g_7 = (8^3)×3 + (8^2)×3 + 8×2 + 7 = 1751
となります. g_6 → g_7 も "繰り下がり" が起きているので詳しく見ましょう.
g_6 = (7^3)×3 + (7^2)×3 + 7×3
→ g_7 = ((8^3)×3 + (8^2)×3 + 8×3) - 1 = (8^3)×3 + (8^2)×3 + 8×2 + 7
8×3 - 1 では 8×3 が崩されて 8×2 + 7 になります.
ここまで説明した列は, 初期値を 5 として得られる数列ですが, 初期値を他の自然数で定めればまた別の数列が得られることは了解されるでしょう. 小さい初期値の数列を少し見ていきます.
初期値 2: g_1 = 2, g_2 = 3 - 1 = 2.
g_3 は "g_2 の遺伝的 3 進表記の 3 を 4 に置き換えて -1" ですが, 3 は現れないため置き換えは行われません.
g_3 = 2 - 1 = 1
g_4 = 1 - 1 = 0
すると g_4 = 0 となりました. グッドスタイン列の項を計算していく途中で, g_n = 0 となった場合, そこで終了と約束します. つまり初期値 2 のグッドスタイン列は g_4 = 0 で終了します.
初期値 3:
g_1 = 3 = 2 + 1
g_2 = (3 + 1) - 1 = 3
g_3 = 4 - 1 = 3
g_4 = 3 - 1 = 2
g_5 = 2 - 1 = 1
g_6 = 1 - 1 = 0
初期値 3 のグッドスタイン列は g_6 = 0 で終了します. 初期値 0 と 1 は見ませんでしたが, これもすぐに 0 になって終了することは簡単に確かめられます.
次に初期値 4 を見ましょう. これはすぐには 0 になりません.
初期値 4:
g_1 = 4 = 2^2
g_2 = (3^3) - 1 = 3^2×2 + 3×2 + 2
g_3 = 4^2×2 + 4×2 + 1
g_4 = 5^2×2 + 5×2
g_5 = (6^2×2 + 6×2) - 1 = 6^2×2 + 6 + 5
g_6 = 7^2×2 + 7 + 4
g_7 = 8^2×2 + 8 + 3
g_8 = 9^2×2 + 9 + 2
g_9 = 10^2×2 + 10 + 1
g_10 = 11^2×2 + 11
g_11 = (12^2×2 + 12) - 1 = 12^2×2 + 11
さてここで疑問が生じます. この初期値 4 のグッドスタイン列はいつか g_n = 0 となって終了するでしょうか? それともいつまでも終了せずに無限に計算が続いていくのでしょうか?
これについては既に結果が知られています. n = 3×2^402653211 - 2 で g_n = 0 となるのです. ちなみにもう少し構造がわかる書き方をすると
です.
実際に確かめたわけではありませんが, 初期値 4 のグッドスタイン列が途中で 0 となって終了することを見ました. しかし同様の疑問は全ての自然数で考えることが出来ます.
初期値 n のグッドスタイン列は途中で 0 になって終了するか? それとも無限に続くのか?
この疑問に対する解答を述べるのがグッドスタインの定理 (Goodstein's Theorem) です.
