この記事では三項間漸化式
を解くときに
が出てくることの謎について考察していきます。
私が昔漸化式の勉強をしていたときこのような話を見かけました。
三項間漸化式
は特性方程式
の解
と解ける。
このカラクリについては線形代数の勉強をしていたときに次のような説明を知りました。
上の三項間漸化式は
と表すことができ、右の行列の固有方程式が
となることからある行列
と標準化できる。よって漸化式は
しかしこれだけだと漸化式の特性方程式と行列の固有方程式が一致することの本質的な説明がされておらず、いまいちしっくりきませんでした。
ということで「なぜ
以下では一般の
を考えることにします。
このとき数列空間上の線形写像
行列で表すと
を考えると、上の漸化式を解く問題は
さらに別の線形写像(シフト作用素)
と表すことができます。これを
を解く必要があります。
とおくと
が成り立ちます。
実際
が成り立つので
が成り立ちます。
よって
ここで元の漸化式に戻って
を考えると、左辺に
が成り立ちます。
いま
に他ならないので望遠鏡和(和分)
を繰り返すことで
が得られます。
よって
と解けます。
特に
が成り立ちます。
ちなみにこれらの操作は
と定めると線形写像の演算として
のように書けます。
を因数分解するために特性多項式
を解く必要があり、
と因数分解することで
と解くことができる。という話でした。
これで「なぜ
ついでにいくつかおまけを書いておきます。
では。
一次分数型の漸化式
を解くときも特性方程式
が出てきます。これについても行列によってある程度説明できます。
その前にまずメビウス変換(一次分数変換)と行列の対応について説明します。
複素行列
の複素数
によって定めます。このときこの作用は結合的となる、つまり行列
が成り立ちます。このことは次のように確かめられます。
ベクトル
が成り立つので
さてこれによって一次分数型の漸化式
と解くことができます。
よって
を
なのでこの比を取ることで特性方程式
が出てきます。
また特性方程式が異なる二解
によって
と対角化されるので
とおくと
と等比数列
が得られたりします。
ちなみに
によって
と解けます。この
となります。
今回漸化式を解いたのと同じようにして
も解くことができます。
ここでは関数空間
を考えます。例のごとく
と因数分解すると
が成り立ちます。
そしてライプニッツ則より
が成り立つので
と解けます。