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

漸化式を"解く"とは

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

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

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

1. 第１段階は、漸化式を$g_n$に関する1つの式に書くことである。
   ここで要求されるのは当然場合分けを含まない式である。
   まず、$g_n=g_{n-1}+g_{n-2}$が$n \geq2$について成立する。
   また、$n \leq 0$についても$g_0=0$および$g_{負数}=0$を前提としているので、この式が成立する。しかし$n=1$の場合、左辺が$1$で右辺が$0$なので、この式は不成立となる。だがこの問題は$[n=1]$を右辺に加えることで解決する。
   したがって、全体を$g_n=g_{n-1}+g_{n-2}+[n=1]$とまとめることができる。

2. 第２段階は、この<$g_n$>に関する式を変形して$G(z)$=$\sum_{n}^{} g_nz^n $に関する式を導く段階である。これは比較的容易で
   $$ G(z)= \sum_{n}^{} g_nz^n= \sum_{n}^{} g_{n-1}z^n+ \sum_{n}^{}g_{n-2}z^n+ \sum_{n}^{} [n=1]z^n\\ \,\,\,\,\,\,\,\,\,\,\,\,\,= \sum_{n}^{}g_nz^{n+1}+ \sum_{n}^{}g_nz^{n+2}+z\\ \,\,\,\,\,\,\,\,\,\,\,\,\,=zG(z)+z^2G(z)+z $$

3. 第３段階も第２段階同様、フィボナッチ数列については容易である。
   $$ G(z)= \frac{z}{1-z-z^2} $$

4. 第４段階についてはフィボナッチ数列に関してなら若干感覚的に進められる部分もあるが、より複雑化した漸化式にも対応できるよう手順を踏んでいく。
   母関数$ \frac{z}{1-z-z^2} $を冪級数に展開したとき、$z_n$の係数$ [z^n] \frac{z}{1-z-z^2} $はどうなるか。
   より一般的に、多項式$P$および$Q$について、次の有理関数の係数$[z_n]R(z)$はどうか。
   $$ R(z)= \frac{P(z)}{Q(z)} $$$ $
   有理関数で、その係数が特に良い形をしているものの１つは
   $$ \frac{a}{(1- \rho z)^{m+1}} = \sum_{n \geq 0}^{} \binom{m+n}{m} a \rho ^nz^n $$であろう。また、これと似た式
   $$ S(z)= \frac{a_1}{(1- \rho _1z)^{m_1+1}} +\frac{a_2}{(1- \rho _2z)^{m_2+1}}+ \cdot \cdot \cdot +\frac{a_l}{(1- \rho _lz)^{m_l+1}} \cdot \cdot \cdot(式A) $$の有限個の項の和も、次の良い係数を持っている。
   $$ [z^n]S(z)=a_1 \binom{m_1+n}{m_1} \rho _1^n+a_2 \binom{m_2+n}{m_2} \rho _2^n+ \cdot \cdot \cdot +a_l \binom{m_l+n}{m_l} \rho _l^n $$

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