漸化式を"解く"とは
ここでは、ある漸化式を満たす系列<>が与えられた場合に、をに関して閉じた式で表現することを指す。そしてその問題を母関数を用いて解くとき、充分に機械的な次の4段階を踏むことになる。
- 系列の他の要素でを表すような式を書く。ただしこの式はすべての整数に関して成立しなければならない。ただしという前提を置く。
- 式の両辺ととの積を作り、すべてのについての和をとる。このとき左辺はという和になり、これは母関数そのものである。そこで右辺を操作してに関する別の式が出てくるようにする。
- この方程式を解いて、の閉じた式を求める。
- このを冪級数に展開し、の係数を取り出す。これがの閉じた式である。
この方法で上手くいく理由は、系列<>全体をひとつの関数で表していて、その関数に種々の操作を適用できるからである。
第1段階は、漸化式をに関する1つの式に書くことである。
ここで要求されるのは当然場合分けを含まない式である。
まず、がについて成立する。
また、についてもおよびを前提としているので、この式が成立する。しかしの場合、左辺がで右辺がなので、この式は不成立となる。だがこの問題はを右辺に加えることで解決する。
したがって、全体をとまとめることができる。
第2段階は、この<>に関する式を変形して=に関する式を導く段階である。これは比較的容易で
第3段階も第2段階同様、フィボナッチ数列については容易である。
第4段階についてはフィボナッチ数列に関してなら若干感覚的に進められる部分もあるが、より複雑化した漸化式にも対応できるよう手順を踏んでいく。
母関数を冪級数に展開したとき、の係数はどうなるか。
より一般的に、多項式およびについて、次の有理関数の係数はどうか。
有理関数で、その係数が特に良い形をしているものの1つは
であろう。また、これと似た式
の有限個の項の和も、次の良い係数を持っている。
漸化式概論 破では、である有理関数がすべてと表せる ことを示すことから始める。ただしはで与えた形、は多項式である。