二項間漸化式

概要

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

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

この漸化式は、 と を、とある文字 に置き換えた方程式

の解を用いて、

と書き換えられる。ここで、数列 の各項から を引いた、新しい数列 を考えると、これは公比 の等比数列となり一般項が計算できる。

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

例

漸化式

を解く。そのために、まずは方程式

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

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

と求められる。「等比数列」の辞書を復習したい方はこちらから。

証明

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

が出てきたのかについて考える。これは、与えられた二項間漸化式を、 ある文字 を使って

に変形して、解ける形にしたいなあ、というのが出発点。これを変形すると、

となるので、これが、元の漸化式と等しくなるためには、係数同士を比較して

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

なので、方程式

を解いて出てきた を使うとうまく変形できるという、答えありきな感じで出てきた方程式であった（特に である必要もないのだが、よく を使う）。文章で書かれてもわからん！という方は、ヨビノリさんのこちらの「特性方程式」についての動画がおすすめ。

補足

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

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

のときは、上の特性方程式が解を持たないが、少し数列を考えてみると

• かつ が定数のときは、 等差数列の漸化式
• かつ が の関数のときは、 階差数列の漸化式

となって、基本的に解ける。「等差数列」の辞書はこちらから。「階差数列」の辞書はこちらから。

縄跳びで、二重跳びの後に三重跳びに挑戦するようなイメージで、二項間漸化式をマスターした方は、三項間漸化式にチャレンジしよう。三重跳びよりは簡単。