Search on the blog

2015年2月13日金曜日

漸化式を解く5つの方法

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

How to Solve Recurrence Relations

漸化式の形が

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

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

1.と2.はarithmetic/geometric sequenceなので高校数学で習う。
3.は知らなかった。anはp(n)より1つ高次の多項式になるらしい。
4.は高校のとき習った。特性方程式を解けばいい。

最後に、
5. 母関数を使って一般項を出す方法
も紹介されている。

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

0 件のコメント:

コメントを投稿