漸化式を解く5つの方法

　漸化式を解く5つの方法を纏めた以下のページがなかなかよかった。

How to Solve Recurrence Relations

漸化式の形が

1. a_n = a_n-1 + d
2. a_n = a_n-1 * r
3. a_n = a_n-1 + p(n),  p(n)はnの多項式
4. a_n = 前のk項の線形結合

の場合に、どのように一般項を導出すればよいかが記載されている。

1.と2.はarithmetic/geometric sequenceなので高校数学で習う。

3.は知らなかった。a_nはp(n)より1つ高次の多項式になるらしい。

4.は高校のとき習った。特性方程式を解けばいい。

最後に、
5. 母関数を使って一般項を出す方法

も紹介されている。

せっかくなので、4.と5.の方法を使ってフィボナッチ数列の一般項を求めてみた。
4. で解くほうが断然楽だった。