漸化式について

Question

趣味で数式をいじっていて出てきたのですが、
A 1=2, A n+1=5^n
のような漸化式の一般項{A n}は何ですか。そもそも一般項を求められるのでしょうか。求められた場合は、そこに至る過程まで教えてください。
ご覧になった皆様、どうぞお知恵をお貸しください。

stomachman · Accepted Answer

お楽しみのようですね。
　このご質問（訂正後のやつ）はもしかして：
「えーと、底が5の対数をlogと書くことにして、数列aを
　　a[n] = log(A[n])
と定義すれば、漸化式は
　　a[n+1] = log(5^A[n]) = A[n] log(5) = A[n] = 5^a[n]
というわけで、aは初項以外はAと同じ漸化式になって元の木阿弥、さてどうしたもんか」というようなお話でしょうか。

Aは指数関数よりも速く大きくなる数列で、手懐けようにも対数ぐらいじゃ歯が立たない。ですから、「一般項を求む」って言われても、その一般項を式に書き表す手段が中学高校で習うような記号では追いつかないということです。

しかし特にA[1]=5の場合に限っては、↑↑（tetration.  計算機科学の創始者 D.Knuthによる) という記号を使って一般項が A[n]=5↑↑n と表されます。
　　じゃあ、A[1]≠5の場合にはどうするか。cをm個並べた c × c × … × c を c^m (あるいはKnuthの記号では c↑m)と書く、という話ですと、掛け算は可換なので、cをm個並べたあとに bを掛け算したもの  c × c × … × c × b は b × ( c↑m )とやれる。
　けれども、「cをm個並べた c ↑ c ↑ … ↑ c を c↑↑m と書く」の方は ↑が非可換なので、「 c ↑ c ↑ … ↑ c の後ろに bをくっつけて　 c ↑ c ↑ … ↑ c ↑ b  はどうだ」、となると ↑↑では表せない。

実を言えば ↑↑という演算自体が「cをm個並べた c ↑ c ↑ … ↑ c を c↑↑m と書く」というだけの意味であり、これをキチンと（formalに）言うなら
　　n↑↑1 = n
　　n↑↑m = n^(n↑↑(m-1))
と漸化式で表す以外にない。記号を決めた、というだけに過ぎません。それを「一般項」と呼ぶことを認めちゃうのであれば、ご質問の場合には、こうなります：
　漸化式で定義される関数 B(b,c,n)
　　B(b,c,1) = b
　　B(b,c,n+1) = c^B(b,c,n)
をでっち上げておいて
　　A[n] = B(2,5,n)
とでもする以外に答えようがない、ということです。

このご質問は「一般項」ってそもそもなんだっけ、という疑問を改めてテツガクする必要がある、という所に面白さがあると思います。すなわち「（たまたま）みんなが知ってる書き方だけで間に合う」というのと、どこがどう違うのか。

さらに余談ながら、この漸化式の仕組みを繰り返し使って
　　n+1+…+1 = n+n,  
　　n+…+n = n×n,  
　　n×…×n = n↑n,  
　　n↑…↑n = n↑↑n, 
　　n↑↑…↑↑n = n↑↑↑n, 
　　n↑↑↑…↑↑↑n = n↑↑↑↑n,  
　　 ....
という演算の系列が作れる。いわば漸化式の漸化式です。で、この系列の中のどの演算でも計算できる関数が（もちろん漸化式によって）構成できます。これはAckerman関数と呼ばれ、計算機科学の初歩において漸化式（再帰的定義）の概念を学ぶ教材として、しばしば引き合いに出されます。
　Ackerman関数は（一般項なんて近道なしに）まさしく漸化式の漸化式に忠実に従って、（n×nだろうがn↑↑↑nだろうが）全部n+1（自然数nの次の数）にまで戻ることで計算する。ですから、「ナンデモ来い」という一般性を持つ代わりに恐ろしく遅いアルゴリズムであることが特徴。この一般性（万能性）と効率のトレードオフは、計算可能性の理論と密接な関係があって、結構深い話です。

ありものがたり · Answer

A[1] = 5 なら、クヌースの矢印を使って A[n] = 5↑n だけど...
質問の答えに、よく知られた簡潔な書き方はなさそうな気がする。

masterkoto · Answer

A 1=2, A n+1=5^n
これら自体が一般項

いるまに · Answer

An+1=5^nより
An=5^n-1
となりA1=1なので問題文のA1=2と矛盾が生じるので成り立たない

漸化式について

お楽しみのようですね。

A[1] = 5 なら、クヌースの矢印を使って A[n] = 5↑n だけど...

A 1=2, A n+1=5^n

An+1=5^nより

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング