多項間漸化式

質問

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

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

回答No.16

stomachman

ちょいと観点を変えてみました。

●m+1項間の線形漸化式を、自然数n∈{0,1,2,...}について
(1) ∀n(n≧m→A[n] = ω+Σ{j=1～∞} k[j]A[n-j])
　　ただしk[j]は定数の列で、∀j(j>m→k[j]=0)である。
と書いてみるとどうか。（勿論mは自然数です。）
つまり漸化式の項の数を気にしないで扱ってみるんです。
　初項としてはA[r] (r=0,1,....,m-1) が与えられている。ですから、式を簡単に書けるようにするために、hが負のときにはA[h]=0と決めておきます。∀h(h<0→A[h]=0)です。これでも差し支えありませんでしょ。

●さて、この漸化式をさらに一般化します。任意の自然数s∈{0,1,2,...}について
(2) ∀n(n≧m+s→A[n] = U[s]ω+Σ{j=1～∞} V[s,j]A[n-j-s])
と書いてみます。もちろんs=0の時は(1)式と一致して欲しいので、
(3) U[0]=1、∀j (V[0,j]=k[j])
とします。
　すると、特にs=n-mである場合には
(4) A[n] = U[n-m]ω+Σ{j=1～∞} V[n-m,j]A[m-j]
となり、右辺は与えられた初項A[r] (r=0,1,....,m-1) だけで表されている。したがってこれが一般項の表現になっています。
　言い換えればU[s], V[s,j] (s=n-m)を求めることができればA[n]の一般項が得られる訳です。

●ここで
V[s,j] = V[s-1,j+1]+V[s-1,1]k[j]
U[s]=U[s-1]+V[s-1,1]
という漸化式が成り立つ。
【証明：
A[n] = U[s]ω+Σ{j=1～∞} V[s,j]A[n-j-s]
= U[s]ω+V[s,1]A[n-1-s]+Σ{j=2～∞} V[s,j]A[n-j-s]
= U[s]ω+V[s,1]A[n-1-s]+Σ{j=1～∞} V[s,j+1]A[n-j-1-s]
さて、
∀n( A[n] = U[0]ω+Σ{j=1～∞} V[0,j]A[n-j])
であるから
A[n-1-s] = U[0]ω+Σ{j=1～∞} V[0,j]A[n-1-s-j]
ゆえに
A[n] = U[s]ω+V[s,1](U[0]ω+Σ{j=1～∞} V[0,j]A[n-1-s-j])+Σ{j=1～∞} V[s,j+1]A[n-j-1-s]
= (U[s]+V[s,1]U[0])ω+Σ{j=1～∞} (V[s,1]V[0,j]+V[s,j+1])A[n-1-s-j]
一方U,Vの定義から
A[n] = U[s+1]ω+Σ{j=1～∞} V[s+1,j]A[n-j-s-1]
であり、U[0]=1, V[0,j]=k[j]ですから、
U[s+1]=U[s]+V[s,1]
V[s+1,j] = V[s,j+1]+V[s,1]k[j]
言い換えれば
U[s]=U[s-1]+V[s-1,1]
V[s,j] = V[s-1,j+1]+V[s-1,1]k[j]
証明終わり。】
　U[s]の方はV[s,j]に影響を与えないので、本質的な問題はVだけです。

●つまり
問題：「∀j≧1 , ∀s≧1について漸化式
V[0,j]=k[j]
V[s,j] = V[s-1,j+1]+V[s-1,1]k[j]
ただし∀j(j>m→k[j]=0)
が与えられたとき、V[n-s,j]を求めよ」に帰着します。
　このアプローチだとm次方程式は出番がないはずですし、k[j]が例えば整数の場合に一般項の係数U,Vが全て整数になることも示せると思われます。

●そこで...から後は皆さんにお任せ。

お礼

なんかものすごいことやってくれましたね。
「漸化式の項の数を気にしないで扱ってみる」んですか。
ものすごく数学らしい証明ですね。（と言いつつも実は全く理解できていませんが）
結局「一般」を追求するとこういう結果になるのでしょうか。
とりあえず、じっくり読ませていただきます。
ありがとうございました。