三項間漸化式

概要

漸化式のラスボス。これをスラスラ解けるようになると、心が晴れやかになる。

つの項の間に成り立つ漸化式を三項間漸化式といい、特に と を定数とした、

の形はノーヒントで解けるようにしておく必要がある。

この漸化式は、 を に、 を に、 を に置き換えた方程式

の解（ とおく）を用いて、

と書き換えられる。ここから等比数列の一般項を用いて、数列 の一般項と、数列 の一般項を出して、連立して を消すことで、一般項 が計算できる。

ちょっと何を言っているかわからない人は、下の例で確認しよう。

例

漸化式

を解く。そのためにまずは

を解くと、 なので、与えられた漸化式は

と変形できる。

より、数列 は、初項 、公比 の等比数列なので、一般項は、

となる。

また、 より、数列 は、初項 、公比 の等比数列なので、一般項は、

となる。 から を引くと、

と一般項 が計算できる。「等比数列」の辞書を復習したい方はこちらから。

証明

なぜいきなりこのような方程式

が出てきたのかについて考える。

与えられた三項間漸化式を、 ある文字 を使って

という等比数列の漸化式の形に変形して、解ける形にしたいなあ、というのが出発点。これを変形すると、

となるので、これが、元の漸化式と等しくなるためには、

となるような を見つければ良い。

解と係数の関係より、 は、とある についての方程式

という方程式の解になる（これが突如現れた二次方程式の正体！）。

なので、この方程式を解けば、解の を使ってうまく上のように変形できるという、なんだか答えありきな感じで出てきた方程式であった（特に である必要もないのだが、よく を使う）。

文章じゃよくわからん！とプンスカしている方は、例えばぶおとこばってんの動画を見てみよう。

方程式が重解を持つ場合

上の二次方程式が重解を持つ場合は、解が1種類しか出てこないので、漸化式を1種類にしか変形しかできないことになる。ただその場合でも、頑張って解くことはできる。

例えば、漸化式

を解いてみる。このとき特性方程式

を解くと、 の重解なので、与えられた漸化式は

と変形できる。よって、数列 は、初項 、公比 の等比数列なので、一般項は、

となる。

次のステージとして、この漸化式を直接解いて、数列 の一般項を求めにいく。

上の漸化式の両辺 で割ると、

となるので、

とおけば、

を得る。

これはつまり数列 が等差数列であることを意味していて、この一般項は簡単に求められる。初項 であることを踏まえると、

と求められる。よって、求める数列 の一般項は、

となる。

補足

漸化式を解く際は、自分で を計算してみて、 一般項の答えがあってそうかどうか確認できるので、安心感がある。

二項間漸化式のときと同様、方程式

は、特性方程式とも呼ばれる。