4

フィボナッチ数列に関する漸化式概論 序

261
0

漸化式を"解く"とは

ここでは、ある漸化式を満たす系列<gn>が与えられた場合に、gnnに関して閉じた式で表現することを指す。そしてその問題を母関数を用いて解くとき、充分に機械的な次の4段階を踏むことになる。

  1. 系列の他の要素でgnを表すような式を書く。ただしこの式はすべての整数nに関して成立しなければならない。ただしg1=g2==0という前提を置く。
  2. 式の両辺とznとの積を作り、すべてのnについての和をとる。このとき左辺はngnznという和になり、これは母関数G(z)そのものである。そこで右辺を操作してG(z)に関する別の式が出てくるようにする。
  3. この方程式を解いて、G(z)の閉じた式を求める。
  4. このG(n)を冪級数に展開し、znの係数を取り出す。これがgnの閉じた式である。

この方法で上手くいく理由は、系列<gn>全体をひとつの関数G(z)で表していて、その関数に種々の操作を適用できるからである。

フィボナッチ数列

与えられる漸化式はg0=0    g1=1    gn=gn1+gn2(n2)である。

  1. 第1段階は、漸化式をgnに関する1つの式に書くことである。
    ここで要求されるのは当然場合分けを含まない式である。
    まず、gn=gn1+gn2n2について成立する。
    また、n0についてもg0=0およびg=0を前提としているので、この式が成立する。しかしn=1の場合、左辺が1で右辺が0なので、この式は不成立となる。だがこの問題は[n=1]を右辺に加えることで解決する。
    したがって、全体をgn=gn1+gn2+[n=1]とまとめることができる。

  2. 第2段階は、この<gn>に関する式を変形してG(z)=ngnznに関する式を導く段階である。これは比較的容易で
    G(z)=ngnzn=ngn1zn+ngn2zn+n[n=1]zn=ngnzn+1+ngnzn+2+z=zG(z)+z2G(z)+z

  3. 第3段階も第2段階同様、フィボナッチ数列については容易である。
    G(z)=z1zz2

  4. 第4段階についてはフィボナッチ数列に関してなら若干感覚的に進められる部分もあるが、より複雑化した漸化式にも対応できるよう手順を踏んでいく。
    母関数z1zz2を冪級数に展開したとき、znの係数[zn]z1zz2はどうなるか。
    より一般的に、多項式PおよびQについて、次の有理関数の係数[zn]R(z)はどうか。
    R(z)=P(z)Q(z)
    有理関数で、その係数が特に良い形をしているものの1つは
    a(1ρz)m+1=n0(m+nm)aρnznであろう。また、これと似た式
    S(z)=a1(1ρ1z)m1+1+a2(1ρ2z)m2+1++al(1ρlz)ml+1(A)の有限個の項の和も、次の良い係数を持っている。
    [zn]S(z)=a1(m1+nm1)ρ1n+a2(m2+nm2)ρ2n++al(ml+nml)ρln

漸化式概論 破では、R(0)である有理関数R(z)がすべてR(z)=S(z)+T(z)と表せる ことを示すことから始める。ただしS(z)(A)で与えた形、T(z)は多項式である。

投稿日:202141
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

橋本環奈です。

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中