多項間漸化式

数学の授業で3項間漸化式をやったとき
ふと4項間漸化式の一般項が知りたくなりました。
しかしいろいろ試しましたが分かりません。
質問No.84673の「4項間漸化式」も見させていただきましたが、
結局、漸化式の問題ではないという感じで終わっていてよく分かりません。

たとえば3項間ならば特性方程式と二次方程式の解の公式から
a(n+2)-(α+β)*a(n+1)+αβ*a(n)=0 となるα,βを求め(α≠β)
(

No.8 回答者： motsuan 回答日時： 2001/06/17 02:30

やるんじゃないかと思っていましたが、漸化式は

a(n)-{α(1)+α(2)+...+α(k-1)+α(k+1)+...+α(N)} a(n-1)
+ ... + (-1)^(N-1) α(1)α(2)...α(k-1)α(k+1)...α(N) a(n-N+2)
=α(k) [ a(n-2) +{α(1)+α(2)+...+α(k-1)+α(k+1)+...+α(N)} a(n-3)
　　　　　+ ... + (-1)^(N-1) α(1)α(2)...α(k-1)α(k+1)...α(N) a(n-N+1) ]
(k=1,...,N)　（＊）
ですね。訂正いたします。

ついでですので
KanjistXさんが質問で例にあげてらっしゃる３項の場合ですと、
a(n)-αa(n-1)=β^(n-1) {a(1)-αa(0)}
a(n)-βa(n-1)=α^(n-1) {a(1)-βa(0)}
から、辺々を加えて
2a(n)-(α+β)　a(n-1) = (α^(n-1) +β^(n-1) ) a(1)-(αβ) (α^(n-2) +β^(n-2) ) a(0)
となって、係数が全部、対称になってα+βとαβで書けちゃうのでは？
つまり、解自体を目にすることなく回答にたどり着けるということです
（実際は (α^(n-1) +β^(n-1) ) を消すのは大変だと思いますが）。
ありゃ？右辺がｎを含むんですね。
その意味では（＊）にｎを含んだ項Ω(n）を付け加えなくてはいけないですね。
でも、No.6のstomachmanさんの解法を用いればいいので
一般の場合も問題ないと思います．．．（かなり弱気）。
（やっぱり、はじめるとこういう手落ちが多いので．．．情けないやらお恥ずかしいやら）

この回答へのお礼

お礼が遅れまして申し訳ありません。
No.7も含めて印刷して読んでいたのですが、なかなか理解できなくて…。
まあ、うっすらとは理解できました。
No.11でstomachmanさんもあのように仰られていることだし。
具体的例も提示していただいたことだし、もう少し考えてみます。
回答ありがとうございました。

お礼日時：2001/06/18 18:47

No.7 回答者： motsuan 回答日時： 2001/06/17 01:09

KanjistX さんこんにちは

まず、先ほど「怒らせる」と書いてしまいましたが、ミスタイプで「怒られる／怒らせてしまう」の間違いでした。
なんか喧嘩うっているような言い方ですよね。ちょっとどうしようかとおもっていましたので、
補足と合わせて書きこませていただきました。

私の回答（No.5）に対する質問の件ですが、
端的にいうと、一般項を解を実際にもとめずに、解｛α,β,・・・,ω}をパラメータとして
含んだ形で得ると、その式は対称性をもつため、解と係数の関係を用いて表されるので、
5次以上であっても一般的に解がえられるのでは ? という意味です。

数列 { a(n) } のa(n),...,a(n-N+1) のN個の項で作られる漸化式に対応する方程式
Σc(k) x^k = 0 (k=0～Nの和)
の解を｛α(1),α(2),...,α(N)}として漸化式を変形して
a(n)-{α(1)+α(2)+...+α(k-1)+α(k+1)+...+α(N)} a(n-1)
+ ... + (-1)^(N-1) α(1)α(2)...α(k-1)α(k+1)...α(N) a(n-N+2)
=α(k) [ {α(1)+α(2)+...+α(k-1)+α(k+1)+...+α(N)} a(n-2)
　　　　　+ ... + (-1)^(N-1) α(1)α(2)...α(k-1)α(k+1)...α(N) a(n-N+1) ]
(k=1,...,N)　（＊）
という連立漸化式（？）ですよね。
(このとき、｛α(1),α(2), ... ,α(N)}を置換して
　α(1)=α(j1), α(2)=α(j2), ... , α(N)=α(jN) としてそれを
　連立漸化式にいれても（＊）全体としてはかわらないですよね。
　本論とはあまり関係がありませんね。）
それを解くと、それぞれ等比級数となって、
a(n),...,a(n-N+2) のN-1個の項でつくられる漸化式がN個できますよね。
これは本論と関係があるのですがここまでは、｛α(1),α(2), ... ,α(N)}を
変数として含む形で計算が進められますよね。
ついでに、得られた式の組は｛α(1),α(2), ... ,α(N)}の置換に対して
N-1個の連立漸化式全体としては変わらないですよね。
したがって、たとえば見通しがいいように、それらの辺々を全部足すと、
a(n),...,a(n-N+2) のN-1個の項でつくられる漸化式で、かつ、
｛α(1),α(2),...,α(N)}の対称式のみを係数とするような数列が得られると思います
（なんといっても、もともとの連立漸化式がそういう対称性をもっているわけですから）。
そして、解と係数の関係からその式はΣc(n) x^n = 0の係数を使って表せるわけで
方程式の解を実際に解の公式で表される数（べき根拡大した数）で得られなくても計算ができるということです。
結局、a(n),...,a(n-N+2) のN-1個の項とΣc(k) x^k = 0の係数でつくられる漸化式が得られ
それを順次解いていけば良いわけですから、数学的帰納法から、
最終的な一般項（一般式といってしまってましたね）を
解の公式で表される数（べき根拡大した数）を経ずに得られることになると思います
（もちろん解の公式がない場合でも）。

つまり、上で得た一般式の最終的な形は、代数的に係数でつくられる数
の範囲に入っているのではないの？という意味です。

No.6 回答者： stomachman 回答日時： 2001/06/16 22:30

masuo_kunさん

> 「余り」はｎの式
大したことないですよ。下記をご覧じ。

Ωを既知の数列とするとき、
(1)　A(n)=αA(n-1)+Ω(n-1) (α≠1)
という漸化式の一般項は
(2)　A(n)=(α^n)A(0)+(Σ{j=0～n-1}(α^j)Ω(n-1-j))
と表されます。
　特にΩ(n)=ωのとき、漸化式は
(1')　A(n)=αA(n-1)+ω
であって、
(2')　A(n)=(α^n)A(0)+ω((α^n)-1)/(α-1)
=(α^n)(A(0)+ω/(α-1))-(ω/(α-1))
という一般項を持ちます。これはP=A(0)+ω/(α-1), p=-(ω/(α-1))とおけば
(2'')　A(n)=(α^n)P+p
と書けます。α=1の場合はもっと簡単ですね。

(3)　B(n+1)-βB(n) = α(B(n)-βB(n-1))+Ω(n-1)
という漸化式を考えます。
(4)　A(n)=B(n+1)-βB(n)
と定義することによって、
(2)　A(n)=αA(n-1)+Ω(n-1)=(α^n)A(0)+(Σ{j=0～n-1}(α^j)Ω(n-1-j))
と表せます。さて、Aの一般項が分かったので、(4)を用いて漸化式
(5)　B(n) = βB(n-1)+A(n-1)
が得られた。(5)の一般項は、(2)によって、
(6)　B(n) =(β^n)B(0)+(Σ{j=0～n-1}(β^j)A(n-1-j))
です。特にΩ(n)=ωのとき、
(6')　B(n) =(β^n)B(0)+(Σ{j=0～n-1}(β^j)(α^[n-1-j])P+p)
=(β^n)(B(0)+P/(β-α)+p/(β-1))-(α^n)P/(β-α)-p/(β-1)
となります。
漸化式(3)を整理すると
(3')　B(n+1)-(α+β)B(n)+αβB(n-1)= Ω(n-1)
ですから、一般に
(7)　B(n+1)-bB(n)+cB(n-1)= Ω(n-1)
の形の漸化式は全てこのやり方で扱えることが分かる。連立方程式
b=α+β
c=αβ
が解ければα, βが決まり、これは
α^2-bα+c=0
の一つの解を求めることで解けます。

同様にして
(8)　C(n+2)-βC(n+1)+γC(n)=α(C(n+1)-βC(n)+γC(n-1))+Ω(n-1)
も
(9)　A(n)=C(n+2)-βC(n+1)+γC(n)
と定義すると
(1)　A(n)=αA(n-1)+Ω(n-1)
となり、その一般項は(2)。従って、
(10)　C(n+2)-βC(n+1)+γC(n)=A(n)
で定義されるCの一般項を求めれば良い。これは既に解いてあります。
かくて、
(8')　C(n+2)-(α+β)C(n+1)+(αβ+γ)C(n)-αγC(n-1)=Ω(n-1)
という形の漸化式の一般項が求められた。だから一般に
(9)　C(n+2)-bC(n+1)+cC(n)-dC(n-1)=Ω(n-1)
は、
b=α+β
c=αβ+γ
d=αγ
という連立方程式が解ければ一般項が求められ、これは３次方程式
α^3-bα^2+cα-d=0
の一つの解を求める問題に帰着します。

D(n+3)-βD(n+2)+γD(n+1)-δD(n)=α(D(n+1)-βD(n+1)+γD(n)-δD(n-1))+Ω(n-1)
も全く同様で、従って一般に漸化式
D(n+3)-bD(n+2)+cD(n+1)-dD(n)+eD(n-1)=Ω(n-1)
の一般項は４次方程式を解ければ求められる。

しかし、
E(n+4)-bE(n+3)+cE(n+2)-dE(n+1)+eE(n)+fE(n-1)=Ω(n-1)
から
E(n+4)-βE(n+3)+γE(n+2)-δE(n+1)+εE(n)=α(E(n+3)-βE(n+2)+γE(n+1)-δE(n)+εE(n-1))+Ω(n-1)
を満たすα,β,...,εを得るには、
b=α+β
c=αβ+γ
d=αγ+δ
e=αδ+ε
f=αε
を解く必要があり、これは一般に５次方程式の一つの解を求める問題になります。

この回答へのお礼

詳しい回答ありがとうございます。
印刷してじっくり読みたいと思います。
なんか、話がだいぶ広がってきましたね。
わくわくしてまいりました。
一つ答えていただけるならば「Ωを既知の数列とするとき」というのがよく分かりませんので教えていただきたいです。

お礼日時：2001/06/17 13:40

No.5 回答者： motsuan 回答日時： 2001/06/16 10:55

KanjistXさんこんにちは

guiterさんの鮮やかな解法に見とれて
怒らせそうですが感じたことを書きます。

　guiterさんの解法では、連立した等比級数が現れて、
解α、β、γ、・・・を置換する（並べ替えて代入する）と
互いに移りあって、連立方程式は全体として変わらないようですよね。
そして、そこから導かれるα、β、γ、・・・を含んだ一般式は、
α、β、γ、・・・を置換しても
変わらないのではないでしょうか（cyclicという部分です)。
（但し未確認です。guiterさんの示された解をみて
　あてずっぽうにいっているだけです。）

　方程式の係数（漸化式の係数）も同じ性質（置換してもかわらない）を満たし、
かついろいろなバリエーションを十分含んでいる（基本対称式になっている）ので
その係数を使って一般式を表すことができるのではないでしょうか？
（つまり、ちゃんとした数として一般式を表すことができるということです）
（そう言えば、高校で勉強する二次式の場合は、
　解と係数の関係を使って、最後まとめていたような
　・・・う～ん年を取ってしまったぁ！）

具体的にどうなのかといわれると計算力がないもので許してください。

この回答への補足

え？対称式として複数の式が立つから連立して解けるんですよね。
すみませんが、いまいちmotsuanさんの言わんとするところが見えません。

補足日時：2001/06/16 23:08

No.4 回答者： noname#598 回答日時： 2001/06/16 07:42

>guitarさん

お考えいただいたのに勝手に締め切ってしまってごめんなさい。
なるほど、すごくためになりました。
>stomachmanさん
具体的な解を書いてくださってありがとうございます。
どうやらそうなるらしい、ということはわかりました。
でも大学の知識がすっぽり抜けてしまったので、確認できないことをお許しください。
お２人に私がポイントを差し上げることはできませんが感謝します。

一般の５項間以上のものですが、
私もstomachmanも述べたとおり、解を作る公式が存在しないので、
guitarさんのお示しの方法も折角ですが６項間以上では通用しないんです。
私が求めていたのも行く末はｎ項間漸化式でしたが、私自身が以上のことに気づいてしまったことと、仮にその方法でｎ項間漸化式が解けたとしても、今度はｎ－１項間漸化式が待っているに気づいた(しかも「余り」はｎの式である)ので、
そこでお手上げ（面倒くせ～～・・・）になってしまい、やめちゃったんです。
質問者がこうなってしまっては新たに回答を求めることは失礼だと思ったので、締め切りました。

ということで、このご質問に対する最も適当な回答は、
「隣接５項間までなら可能、それ以上なら一般には不可能」ですね。どうやら・・・

この回答へのお礼

なんかまるでmasuo_kunさんの質問掲示板になってしまいましたね（笑）
僕自身誰にポイントを差し上げようかと迷っている次第です。
けれど、皆さんの回答のおかげでいろいろと勉強になって
感動も多く味わわせていただいております。
もう2,3日締め切りを待ちますので
（というより、皆さんの回答を理解してからお礼やポイント進呈をしたいので）
まだ何か言いたい方はどしどし回答お願いいたします。
（可能ならば高校生の僕にも分かる範囲でお願いします）

お礼日時：2001/06/16 22:58

No.3 回答者： stomachman 回答日時： 2001/06/16 00:40

な～るほど。

　引き続く(m+1)項の線形和で表される漸化式
K[m] A(n+m) + K[m-1]A(n+m-1) + ... + K[0]A(n) = δ
なら
K[m] x^m +K[m-1] x^(m-1)+ .......+ K[0] = 0
の(m+1)個の解が具体的に得られさえすれば、処理できますね。（K[j] (j=0,1,2,...,m)とδは定数。）δ=0に限る必要はないと思います（余計な項が出てくるけど）。
しかし５次以上になると、一般には解析的には解けないんでした。

　さて、質問No.84673の「4項間漸化式」に出てくる漸化式
A(n+3)-A(n+2)-A(n+1)-A(n)=0
の場合には、
A(n+3)-(α+β+γ)A(n+2)+(αβ+βγ+γα）A(n+1)-αβγA(n)=δ
ここに
U=(19/27-√(11/27))^(1/3)
V=(19/27+√(11/27))^(1/3)
として
α=1/3+(U+V)
β=1/3-(U+V)/2-i(√3)(U-V)/2
γ=1/3-(U+V)/2+i(√3)(U-V)/2
δ=0
という事になるはず。どうでしょうか。

この回答へのお礼

う～ん。線形和ですか。これは僕に対する回答というより、
masuo_kunさんに対する回答と受け取った方がよさそうですね。
すみません。90%以上が理解できない内容なのです。
なんともいえません、うぐぅぅ～。

お礼日時：2001/06/16 22:46

No.2 回答者： guiter 回答日時： 2001/06/16 00:21

masuo_kun さん、前回は締め切りに間に合いませんでした。

前回の a(n+3)=a(n+2)+a(n+1)+a(n) については下のやり方で出来ました。

４項間漸化式において３次方程式が３つの異なる解を持つ場合は、
次のようにすれば良いと思います。
３つの解をαβγとします。
すると、
　a(n+3)-(α+β)*a(n+2)+αβ*a(n+1)=γ{a(n+2)-(α+β)*a(n+1)+αβ*a(n)}
　a(n+3)-(β+γ)*a(n+2)+βγ*a(n+1)=α{a(n+2)-(β+γ)*a(n+1)+βγ*a(n)}
　a(n+3)-(γ+α)*a(n+2)+γα*a(n+1)=β{a(n+2)-(γ+α)*a(n+1)+γα*a(n)}
のように変形できるので、これらから
　a(n)＝-1/{(α-β)(β-γ)(γ-α)}*[(β-γ){a(3)-(α+β)*a(2)+αβ*a(1)}α^(n-1)　＋　cyclic ]
のように出てきます。

５項間の場合も４つの解αβγδを持つ場合は
　a(n+4)-(α+β+γ)*a(n+3)+(αβ+βγ+γα)*a(n+2)-αβγ*a(n+1)=δ{a(n+3)- …}
などとすれば良いのではないでしょうか。
それ以上も同様に考えれば出来ると思います。（一般にではないですけどね）

この回答へのお礼

いやはや感動いたしました。
こんなにきれいに左辺と右辺に分配できるんですね。
途中で気づきましたが、
n項間漸化式について
各係数は(n-1)次方程式の解α,β,γ,δ,…についてのk次の輪環の和なんですね。
だからこそ、
a(n+3)-(α+β)*a(n+2)+αβ*a(n+1)=γ{a(n+2)-(α+β)*a(n+1)+αβ*a(n)}のように
2次方程式の解と係数の関係式に
新たに加わった解γを右辺にかけるといったような単純作業で分配できるんですね。
僕にとってはこれ以上何も言うことはありません。
本当にありがとうございました。

お礼日時：2001/06/16 22:38

No.1 回答者： noname#598 回答日時： 2001/06/15 23:28

はい、No.84673の質問者です（笑）

４項間漸化式においては、
a(n+3)-α*a(n+2)-βa(n+1)=γ{a(n+2)-α*a(n+1)-βa(n)}
を満たすα、β、γが存在すればきれいに行くんだと思います。
ただし、私が質問したあの設定の場合は、３次方程式の解の公式に入れなくては解けません。
つまり、これが５項間、６項間・・・ともなると、伴って
5次方程式、６次方程式・・・が出てくることが予想されます。
この辺は「解の公式は存在しない」世界なので、一般に解くことは不可能と思われます。

実は３項間でも、a(n+2)=２a(n)のような隣接でないやつはだめですし、
（一般には偶数番目と奇数番目で場合分けする）
隣接３項間でも、a(n+2)=a(n+1)-a(n)
なんてシロモノもありますよね。
（もちろん、これは無理すれば解けますが、数Ａだけの知識では無理な範囲）

で、漸化式がでてくれば、それでいいじゃない、という結論で終わったのは、
あとはコンピュータにやらせときましょ、的な発想で、
もちろんｎ番目を一般にあらわすことはできないけど、
漸化式がでた、ということは普通のプログラムならFor Loopを使えばいいですし、
Excelやロータスのような表計算ソフトであればもっと簡単なんです。
たとえば有名なフィボナッチ数列
a1=1,a2=1,a(n+2)=a(n+1)+a(n)ですら、
a1とa2のセルには１を入れる
a3には、=a1+a2
と入力し、あとは下にこの式をコピーすれば、知りたいところまで計算可能ですよね。
有限個だったらこれで十分対応できますし、この式をとっておけば、
初項２つを入力しなおすだけで、バっと新しい数列ができますし。
（私の質問した内容も、これとまったく同じように対処できることは知っていましたが、あえてどうなんだろうって質問したのです。）
だから、あれはあれで終わってしまったのです。

一般項が求められるということも大切なのでしょうが、
コンピュータの世界では、漸化式が出てくればそれで十分だということでした。

蛇足ですが、私が２番目に出したa(n+2)=a(n+1)-a(n)
ですが、a1=0,a2=1のときは、
a(n)=[{(1-√(3)i)/2}^(n-1)-{(1+√(3)i)/2}^(n-1)}^(n-1)]*i/√3
だそうです。これが整数であることを証明するなんてのも面白そうですが・・・
（ド・モアブルの定理を使えば簡単です。数Ｂで習います）
１つの話題からいろんな知識が要求されて、
高校時代にはつながりもしなかったジャンルが、思わぬところでつながる。
これが数学の面白さなんだなって、学生時代に思いました。

長々とすいませんでした。

この回答へのお礼

きっとmasuo_kunさんが来てくれると思っておりました。
というか期待しておりました。
guiterさんの回答を見させていただいたのですが、
a(n+3)-α*a(n+2)-βa(n+1)=γ{a(n+2)-α*a(n+1)-βa(n)} は間違いですよね。
式を変形しても、3次方程式の係数(α+β+γ),(αβ+βγ+γα),αβγが出てきません。
あとついでですが、
a(n)=[{(1-√(3)i)/2}^(n-1)-{(1+√(3)i)/2}^(n-1)}^(n-1)]*i/√3 も
a(n)=[{(1-√(3)i)/2}^(n-1)-{(1+√(3)i)/2}^(n-1)}^(n-1)]/i*√3 ですね。

特殊な3項間漸化式ですが、僕も同じようなことを考えていました。
特に、a(n+2)=a(n+1)-a(n)といった虚数を含む一般項式には興味がありました。
ド・モアブルの定理は来月頃に習うので、まだやっていませんが、
教科書等を見て極形式に変換したりしながら何とか自力で解きました。
最終的にn*(-60°)を60°120°180°240°300°360°に場合分けしましたが、
a(n)が整数となることが分かりました。
幅広い数学のお話をありがとうございました。

お礼日時：2001/06/16 21:40