概要
高校でならう数列と漸化式は、基本的にパターンを覚えるだけ。 高校のとき先生が、漸化式のパターンとその解き方一覧みたなプリントを1枚くれたんですけど、 それがすごくよかったです。
収束値
まあ、パターン丸暗記以外に、いくつか覚えるこつはあって、 そのうちの1つは収束値という考え方。 例えば、以下のような漸化式を考えてみます。
| 1 |
| 2 |
解き方のパターンとしては、 an + 1 = an = x と置いて、x の値を求めろって言われます。 まあ、意味はよく分からないけども、それで解けることが経験的に知られているんで。 でも、 an + 1 = an = x と置くことに意味がないこともない。
もし、この漸化式によって定まる数列 an が、 n → ∞ のときにある値に収束するとすると、 an だけでなくて、 an + 1 も同じ値に収束するわけです。 この値を x とでも置くと、 元の漸化式から、
| 1 |
| 2 |
ですから、これを解いて、x = −2 になります。 an はこの値に収束するわけですから、 an + 2 は、0 に収束します。
0 に収束する数列と言うと、ぱっと思いつくのは等比数列で、 実際、この場合、an + 2 は等比数列になっています。
| 1 |
| 2 |
an + 1 = an = x と置くのは、要するに、収束値を先に求めちゃってるわけです。 ただまあ、同様の解き方が、収束しない数列の場合にも使えちゃうということですね。 例えば、
は、同じく（収束を仮定した場合の）収束値は x = −1 になるわけで、 an + 1 が等比数列になるんですが、
となって、これは収束はしない数列になります。 （この場合は、本当は収束値ではなくて、振動の中心点が x = −1 になる。） でもまあ、漸化式を解くことはできます。
斉次式
前項で、数列が収束しない場合でも、収束値に相当する値を先に求めてしまうことで漸化式が解けると説明しました。 収束しないんだから収束値を先に求めているという考え方はできませんが、 この場合は斉次式という物を使って説明できます。 （斉次式のよみは「せいじしき」。次数がそろってるという意味。同次式という言い方も。） 先ほど例に挙げた漸化式を再び考えて見ます。
このうち、定数項を除いた部分の
を元の漸化式の斉次式（あるいは斉次項）といいます。 添え字の部分の違いを除けば、全部の項に a がそろって出てきているのでこう呼びます。
ここで、an を、斉次式の解 a'n とその他の部分 x に分けて考えてみましょう。 an = a'n + x と置いて、漸化式に代入すると、
と、斉次式と、 an + 1 = an = x と置いて得られた式に分解されます。
要するに、この手の非斉次項が定数の漸化式は、
- 斉次式の解を求める。
- an + 1 = an = x と置いたときの x の値を求める。
という2段階で解けることになります。
特性方程式
ちなみに、定数係数の斉次な漸化式（元から斉次項しかない漸化式）の解は、 漸化式の階数によらず冪関数になることが知られています。 ここでは、2階の漸化式（高校風に言うと、3項間漸化式）を例にとって説明してみましょう。 2階の斉次漸化式、
を考えてみましょう。 （ただし、p, q は定数。） 最初に言ったように、これの解は冪関数 an = A xn （x, A は n によらない定数。） というような形の数列になることが知られています。 これを元の漸化式に代入してみると、
となりますが、これを両辺 A xn で割ると、
となります。 これは、元の漸化式の an + k の部分を xk に置き換えた物になります。 この式を、漸化式の特性方程式と呼びます。 見ての通り、定数係数の斉次漸化式を解く問題は、 代数方程式を解く問題に帰着されます。
2階漸化式の場合、特性方程式は2次式になりますので、当然、答えも2つ出てきます。 したがって、正確には、漸化式の解は、特性方程式の2つの解をそれぞれ α, β として、 A αn + B βn （A, B は初期値によって決まる定数） という形になります。 （ちなみに、重解の場合は A αn + B n αn ）
ちなみに、漸化式から特性方程式を得る操作は、 「Z 変換」という物を使って説明することもできます。 参考： 「Z変換」 。
虚数解の場合
漸化式の特性方程式が虚数解を持つ場合、 その一般解となる数列は周期性を持ちます。 例えば、以下のような漸化式を考えてみましょう。
特性方程式を解いてみる前に、 ちょっと別の解法をみてみましょう。 一工夫必要なんですが、 添え字 n を1つずらした物を用意して、 元の漸化式との差を取ります。
はい、見ての通り、 an + 3 = an となりますんで、 3項に1回、同じ値が出てくる周期を持った数列になります。 もちろん、最初の2項が実数ならば、全部の項が実数です。
それでは、これを特性方程式の考え方を使って解いてみましょう。 この漸化式の特性方程式は x2 + x + 1 = 0 で、解は1の3乗根になります。 なので、1の3乗根（の1以外の2つ）を ω, （文字の上のラインは共役複素数を表すものとする）と置くと、 一般解は、
定数 A, B は最初の2項の値から求めます。
これらの式から、 a1, a2 が実数ならば、 B = という関係が成り立つことが分かります。 したがって、
となって、ちゃんと全ての項が実数になります。 しかも、ω は1の3乗根なので、 ωn は3回に1回同じ値になるわけで、 上述の、一工夫して解いた結果とは矛盾しません。 （というよりも、上の工夫は、 「特性方程式の解が1の3乗根になるんだから、周期3の数列になるはず」 → 「じゃあ、 an + 3 = an になるはずだから、そうなるように式を変形しよう」 という発想から来ます。）
行列
2つの数列が同時に出てくるような漸化式だって考えられます。 例えば、以下のようなもの。
数Cで習う「行列」を使うと、以下のようにも書けます。
| an + 1 |
| bn + 1 |
| p | q |
| r | s |
| an |
| bn |
これは、
| an |
| bn |
| p | q |
| r | s |
（ベクトルを太字アルファベットで表します。） というように、ベクトルの数列 an と、 行列の係数 A を使って、
とも書けるわけですが、 これの一般解は、
と書けて、 結局、行列の n 乗問題に帰着されます。
数列の数が増えても同様です。 何個だろうと、定数係数で斉次な限り同じ論法で解けます。 （ただし、3×3 以上の正方行列の n 乗計算には、 大学1年レベルの知識が必要。 参考： 「固有値」 。）
ちなみに、前節の定数係数斉次漸化式
も、 bn = an + 1 と置くと、
| an + 1 |
| bn + 1 |
| 0 | 1 |
| −p | −q |
| an |
| bn |
と変形できるので、 結局、行列の n 乗問題として解くこともできます。
定数係数線形漸化式
（書きかけ）
an から an + 1 を作る操作を
と書きましょう。 z は変数ではなく、数列に対して添え字を1つずらす演算子になります。 この記法を使うなら、 漸化式
は、
となります。 このとき、括弧の中身は、 特性方程式に演算子 z を代入したものになっています。
差分演算子 Δ = z − 1。 漸化式の斉次項の階数が1つ増えるけど、 非斉次項に nk があった場合、これの次数を1つ下げれる。
一般的には
係数とか非斉次項が定数の場合には、これまでに説明したような特性方程式とかの考え方を使って、 確実に漸化式から数列の一般解を得ることができます。 でも、 係数が定数でなかったり、 非斉次項が複雑な形をしていたり、 an2 というように非線形（1次じゃない）項があるものになると、 どんな場合でも一般解を得られるような万能の方法はありません。
もちろん、高校の数学の問題として出てくるようなものは解けるものが出てくるわけですが、 それは幸運なケースです。
見方を変えて
数列は、無限次元のベクトルと考えることも可能。 N 次元ベクトルの要素を、 xi（i = 1 ∼ N） と書くのの、i の範囲の制約を取り払った物。
でも、N 階漸化式の解になると、 最初の N 項までの値で数列全体が決まるので、 N 次元ベクトル。
あと、自然数 → 実数の関数とみなすことも可能。
こういう風に、視点を変えたり、制約条件・前提条件が変わったりすると、 同じ物が別の見え方をするということは、数学にはよくあります。 その逆もまたしかりで、 見かけ上全く別の物が、見方一つで同じ物とみなせる場合も多々あります。
