Graviness Blog

算数・数学・科学・電脳・雑記・アホの順の密度で記事が構成されます.
<< January 2018 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 >> ブログランキング・にほんブログ村へ
 
RECOMMEND
ビッグバン宇宙論 (上)
ビッグバン宇宙論 (上) (JUGEMレビュー »)
サイモン・シン, 青木 薫
RECENT COMMENT
  • 豊臣秀吉と曾呂利新左衛門から学ぶ数列の和
    優乃 (07/12)
  • 【誰か解いて】漸化式 a_(n+1) = f(n) * a_n ^ g(n) + h(n) の一般項
    優乃 (02/18)
  • 【誰か解いて】漸化式 a_(n+1) = f(n) * a_n ^ g(n) + h(n) の一般項
    S.S.+ (02/16)
  • 豊臣秀吉と曾呂利新左衛門から学ぶ数列の和
    坂井昭 (03/19)
  • d/dx(x↑↑n): 高さが定数のテトレーションの微分 - 数学的帰納法を用いる方法
    (09/30)
  • 全ての三角形は二等辺三角形
    優乃 (09/28)
  • 全ての三角形は二等辺三角形
    亀レス (09/28)
  • 全ての三角形は二等辺三角形
    優乃 (09/24)
  • 全ての三角形は二等辺三角形
    亀レス (09/23)
  • 【未解決】新しい演算子を創る
    $_ (09/10)
RECENT TRACKBACK
MOBILE
qrcode
PROFILE
無料ブログ作成サービス JUGEM
 
アッカーマン関数(証明編)
アッカーマン関数は、非負整数に対し、次のように定義される関数です。
・・・(A)

本記事では、多重矢印演算子(タワー表記)を使えば、(A) は、次のように表示できることを証明します。(前回の記事の内容については、数学的帰納法で証明しなおします。)
・・・(B)


証明に入る前に以下の2式が成り立つことを示しておきます。
・・・(a)
・・・(b)
(a) の証明
定義より
・・・
(b) の証明
定義より
・・・



以降より、(B) を証明します。i) で、ii) で、iii) で、iv) でを証明します。



i) のとき
非負整数について、以下が成り立つことを数学的帰納法により証明する。
・・・(B-0)

i-1) のとき
(B-0) の両辺にを代入して
・・・
よって、のとき、(B-0) は成り立つ。

i-2) のとき、(B-0) が成り立つと仮定すると
・・・
(A) より
・・・

∴ i-1)、i-2) により、のすべての整数について、(B-0) が成り立つことが証明された。



ii) のとき
非負整数について、以下が成り立つことを数学的帰納法により証明する。
・・・(B-1)

ii-1) のとき
(B-1) の両辺にを代入して
・・・
よって、のとき、(B-1) は成り立つ。

ii-2) のとき、(B-1) が成り立つと仮定すると
・・・
(A) と、(B-0) より
・・・

∴ ii-1)、ii-2) により、のすべての整数について、(B-1) が成り立つことが証明された。



iii) のとき
非負整数について、以下が成り立つことを数学的帰納法により証明する。
・・・(B-2)

iii-1) のとき
(B-2) の両辺にを代入して
・・・
よって、のとき、(B-2) は成り立つ。

iii-2) のとき、(B-2) が成り立つと仮定すると
・・・
(A) と、(B-1) より
・・・

∴ iii-1)、iii-2) により、のすべての整数について、(B-2) が成り立つことが証明された。



iv) のとき
非負整数について、以下が成り立つことを数学的帰納法により証明する。まず、iv-1) で、のときを証明する。iv-2) で、のときを仮定する。
・・・(B-3)

iv-1) のとき
iv-1-1) のとき
(B-3) の両辺にを代入して
・・・
よって、のとき、(B-3) は成り立つ。

iv-1-2) のとき、(B-3) が成り立つと仮定すると
(B-3) の両辺に を代入して
・・・
(A) と、(B-2) より
・・・

∴ iv-1-1)、iv-1-2) により、のとき、のすべての整数について、(B-3) が成り立つことが証明された。よって、のとき、(B-3) は成り立つ。

iv-2) のとき、(B-3) が成り立つと仮定すると
・・・

iv-2-1) のとき
(A) と、(a) より
・・・

∴ iv-1)、iv-2-1) により、のとき、のすべての整数について、(B-3) が成り立つことが証明された。

iv-2-2) のとき
(A) と、仮定した式をもとに、順々に展開していく。
・・・
整理すると
・・・
ここで、とおけば
・・・
となり、以降では、漸化式 を解くことを考える。とおけば
・・・
となり、ここで、iv-2-1) の結果を用いて、初項
・・・
なので、から順に書き出すと
・・・
上記では、(b) を用いた。よって
・・・
ゆえに
・・・

∴ iv-1)、iv-2-2) により、のとき、のすべての整数について、(B-3) が成り立つことが証明された。さらに、iv-2-1) の結果と合わせて、のとき、のすべての整数について、(B-3) が成り立つことが証明された。

∴ i)、ii)、iii)、iv) の結果より、(B) が成り立つことが証明された。Q.E.D.



ここから、余談ですが、(B) は、以下のように書くことで、ものすごく規則性があることに気付きます。
・・・
逆を考えれば、アッカーマン関数は、演算子生成器なのかも知れませんね。また、m=4 辺りから、急激に大きな数になるのも納得です。


関連記事)
アッカーマン関数(模索編)
・アッカーマン関数(証明編)

参考)
アッカーマン関数@wikipedia
クヌースの矢印表記@wikipedia
数学的帰納法@wikipedia

JUGEMテーマ:学問・学校
コメント
from: 優乃   2011/10/24 7:59 PM
怪しい点が一つ。。。

"iv-2-1)" の Ack(k, 1) の展開において、仮定した式を使ってるところ。

仮定した式は、Ack(k, n) ですが、Ack(k, 1) に当てはめてよかったのだろうか。。。
もっというと "iv-2)" で、Ack(k, n) を仮定して良かったのだろうか。。。
from: kariya_mitsuru   2013/06/27 12:36 AM
古い記事へのコメントですみませんm(__)m
2n - 3, if m = 2
となってますが、2n + 3 の誤りではないでしょうか?
from: 優乃   2013/06/27 7:06 PM
kariya_mitsuruさんの指摘通りです。ありがとうございます♪
コメントする









 
トラックバック
この記事のトラックバックURL
http://blog.graviness.com/trackback/949242
 

(C) 2018 ブログ JUGEM Some Rights Reserved.