フィボナッチ数列の一般項

initial-date: 2022/09/11, updated: 2022/12/18

隣接する３項の漸化式（３項間漸化式） \begin{align*} a_{n+2} = p a_{n+1} + q a_{n} \end{align*} で与えられる数列の一般項を求める方法を、いくつか考える。そして３項間漸化式で有名なフィボナッチ数列の一般項を求めてみる。

なお、ここでは第 $n$ 項が $a_n$ であらわされる数列を \begin{align*} (a_n) = (a_0, a_1, \ldots) \end{align*} のように書く。数列というときは、その添え字は自然数であるが、それに $0$ も含めて、$a_0$ から始まるものとする。それを明示したいときには $(a_n)_{n \ge 0}$ と書く。しかしながら、たまに $a_1$ から始まるものを考えることもある。その場合には $(a_n)_{n \ge 1}$ と書く。

また、考察の論理として式を書きあらわす際に、単なる形式的な同値変形と筆者が考えるものは「$\iff$」記号を使う。「$x = 3 \iff x - 3 = 0$」といった具合である。論理の帰結として導く場合には、仮にそれが式の同値変形の結果ではあっても、「$\therefore$」記号をつかう。「$x - 3 = 0 \;\therefore\; x = 3$」といった感じである。

２つの述語が同値であるときも「$\iff$」記号を使う。「$P(x) \iff Q(x)$」という具合であるが、もう少し噛み砕いた「A は a である $\iff$ B が b である」というような使い方もする。述語間の必要条件と十分条件を示す「ならば」という言葉に「$\implies$」という記号を使うときもある。たとえば、「$\{P(x)\;\text{ならば}\; Q(x)\} \iff \{P(x) \implies Q(x)\}$」といった感じである。

なお、本稿ではおそらく使わないだろうが、２つの命題が同値であるときは「$\longleftrightarrow$」記号を、命題間の「ならば」には「$\longrightarrow$」という記号を用いる。述語の場合と区別するためである。

Table of Contents

第０章 漸化式であらわされた数列の「自由度」と一般項

数列 $(a_{n})_{n \ge 0}$ の第 $n$ 番目の項を $n$ の式（関数と言ってもいい）であらわしたものを、一般項と呼ぶ。たとえば、 \begin{align*} a_{n} = 3n + 8\;, \quad b_{n} = 2n^3 + 3n^2\;, \quad c_{n} = 2^n + e^{4n} \end{align*} などである。関数の表記方法を借りれば、$a_{n} = f(n)$ ともあらわせる。

数列の項と項の関係を示したものは、漸化式とよばれる。２つの項の間での関係で示したものは２項間漸化式、３つの項の間での関係で示したものは３項間漸化式という。この考え方を素直に敷衍すれば、$n$ 項間漸化式というものまで考えることができる。

さてこれから、主として３項間漸化式であらわされた数列の一般項をもとめる方法を眺めていくのであるが、漸化式で表現された数列ならではの「自由度（または任意性）」と一般項の関係についてはじめに触れておこうと思う。話をややこしくしないために、 \begin{align*} a_{n+2} = p a_{n+1} + q a_{n} \end{align*} という漸化式で考える。この漸化式からわかることは、あたりまえのことであるが、$a_{n+1}$ と $a_{n}$ が決まらないと $a_{n+2}$ は決まらないということである。この $n$ をどんどん下降させていくと、$a_2$ が決まるためには、$a_1$ と $a_0$ が決まらねばならないということになる。では、$a_1$ はどうやってきまるのか？ $a_0$ は？

すでにあらかたあきらかなように、３項間漸化式そのものからでは、$a_0,\; a_1$ は決定できないのである。逆に言えば、この２つの項の値はどのように決めても良いのだ。そして決まれば、漸化式を利用することにより、全ての項の値がきまる。いや実は、なにも $a_0,\;a_1$ である必要はない。たとえば、$a_3$ と $a_{100}$ の値が決まっていれば、漸化式を適用することによりすべての項が決定できるのだ（証明必要か？必要だろうな。練習問題？）。$a_0$ と $a_1$ は一番わかりやすい例なのである。

このどのように決めても良いものの個数のことを、筆者は「自由度」と呼んでいる（任意性と言ってもいいかもしれない）。３項間漸化式で与えられた数列の自由度は２、２項間漸化式であれば自由度は１、という具合である。この自由度（任意性）の考え方を、数列の一般項表現にも当てはめると、３項間漸化式の一般項は、自由度が２なので未定なパラメタを２個含まねばならないことになる。そして通常は、$a_0$ と $a_1$ がその役割を担う。つまり一般項の表現には $a_0$ と $a_1$ がパラメタとし入っていなければならないのである。２項間漸化式では $a_0$ ひとつ、$n$ 項間漸化式であれば、$a_0,\; a_1,\ldots,\; a_{n-1}$ である。

これから一般項の導出のいくつかの方法を眺めていくが、もとめた一般項が上記の「自由度（任意性）」の個数分の未定のパラメタを保持しているかどうかにも注目である（とりわけ「第２章 シフト演算子を使って解く」での特殊解と一般解の区別のところでこの考え方が役に立っている）。

第１章 漸化式の特性方程式を使って解く

$\blacksquare$ ３項漸化式の特性方程式

数列が３項間漸化式 $a_{n+2} = p a_{n+1} + q a_{n}$ という形で与えられているときに、この一般項を求めることを考えてみる。なお、最初であるから念の為に付け加えておくと、このように書いた場合には、往々にして、$p,\, q$ は、$p \ne 0$ かつ $q \ne 0$ でともに $n$ に依存しないただの定数をあらわしている、とするのが常識的である。$p$ や $q$ が $0$ であると、３項間漸化式として成り立たないのだから、「$p \ne 0$ かつ $q \ne 0$」はもっともな条件であると言える。次に「$n$ に依存しない定数」という物言いであるが、これは単に「定数」といってもいいのだ。ただ、「$p$ は $n$ に依存しない数である」から「定数である」という流れで説明したい、という動機を持っているがゆえに、いきなり紋切りで「定数である」と言いたくない心情があるのである。

初っ端の能書はこれくらいにして、さてここでたてた「一般項を求める」という問題であるけれども、何もことさらに一般項を求めずとも、再帰関数を使ったプログラムを書いて求めればいいではないか、というごもっともな意見はある。しかしそれだとここで終了となってしまって原稿料が稼げない（原稿料があればの話だが）。それに昔はコンピュータはなかった。なので、手元にコンピュータがない時を想定して、筆算で一般項を求めようとしているのである。

とにかく、解けそうな形に持っていく必要がある。数列が等差数列か等比数列であるときの一般項は、わけなく求めることができる。なので、その形に持っていければいいのだけれど、$a_{n+2} = p a_{n+1} + q a_{n}$ という形の３項間漸化式の場合はどうだろうか？

３項間漸化式に少し技巧をいれてみる。一般項を求めやすい等比数列炙り出すための工夫である。そもそもの３項間漸化式は、$a_{n+2} - p a_{n+1} - q a_{n} = 0$ とあらわせるので、この式に対して、 \begin{align*} a_{n+2} - p a_{n+1} - q a_{n} = 0 \iff a_{n+2} - (\alpha + \beta) a_{n+1} + (\alpha\beta) a_{n} = 0 \end{align*} という同値変形ができたとする。体のいい「分割分配」である。すると、最後の結果から \begin{align*} a_{n+2} - (\alpha + \beta) a_{n+1} + (\alpha\beta) a_{n} = 0 \iff \begin{cases} \, a_{n+2} - \beta a_{n+1} = \alpha(a_{n+1} - \beta a_{n}) \\ \, a_{n+2} - \alpha a_{n+1} = \beta(a_{n+1} - \alpha a_{n}) \end{cases} \end{align*} となって、等比数列の漸化式が２つあらわれてくる。実際、$b_{n} = a_{n+1} - \beta a_{n}$ と $c_{n} = a_{n+1} - \alpha a_{n}$ と置き換えると見通しが良くなって、 \begin{align*} & b_{n+1} = \alpha b_{n} \\ & c_{n+1} = \beta c_{n} \end{align*} というように、$(b_{n}),\, (c_{n})$ という等比数列があからさまにわかる。そして、等比数列なのであるからそれぞれの一般項 $b_{n},\, c_{n}$ が \begin{align*} & b_{n} = \alpha^n b_0 \\ & c_{n} = \beta^n c_0 \end{align*} と苦もなく求められ、これらを利用すれば $(a_{n})$ の一般項 $a_{n}$まではあとひと息になる。

実際、この $b_{n}$ と $c_{n}$ を $a_{n}$ を使ってあらわし直すと \begin{align*} b_{n} = \alpha^n b_0 \;\;\iff\;\; & a_{n+1} - \beta a_{n} = \alpha^n(a_1 - \beta a_0) \\ c_{n} = \beta^n c_0 \;\;\iff\;\; & a_{n+1} - \alpha a_{n} = \beta^n(a_1 - \alpha a_0) \end{align*} であり、右辺側を引き算すれば \begin{align*} (\alpha - \beta) a_{n} = (\alpha^n - \beta^n)a_1 + (\alpha\beta^n - \alpha^n\beta)a_0 \end{align*} というようになる。したがって、$\alpha \ne \beta$ であれば、一般項 $a_{n}$ が求められる。任意のパラメタが２個（$a_1$ と $a_0$）入っているので、一般項としての要件は充分に満たしている。はて、$\alpha = \beta$ の場合はどうなるのだ？

道中を振り返ってみよう。ここで導入した $\alpha,\, \beta$ は、式の同値変形からあきらかなように \begin{align*} \begin{cases} \, \alpha + \beta = p \\ \, \alpha\beta = -q \end{cases} \end{align*} でなければならない。これは２次方程式の解と係数の関係そのものをあらわしている、ということに気がつけば、話は早い。つまり、$\alpha,\, \beta$ は \begin{align} x^2 - px -q = (x - \alpha)(x - \beta) = 0 \label{c0.01} \end{align} となるものなのである。これを利用して、$\alpha,\, \beta$ の具体的な値をもとめれば、一般項への道が近くなる。そしてここにあらわれてきた２次方程式を「（３項間漸化式の）特性方程式」という。まとめると \begin{align*} \text{３項間漸化式}\;&:\; a_{n+2} - p a_{n+1} - q a_{n} = 0 \\ \text{特性方程式}\;&:\; x^2 - p x - q = (x - \alpha)(x - \beta) = 0 \end{align*} という関係にあり、この特性方程式の解 $\alpha,\, \beta$ を使えば \begin{alignat*}{2} & b_{n+1} = \alpha b_{n} & &\qquad (b_{n} = a_{n+1} - \beta a_{n}) \\ & c_{n+1} = \beta c_{n} & &\qquad (c_{n} = a_{n+1} - \alpha a_{n}) \end{alignat*} という等比数列の漸化式が導出できるから、あとはこれを解けばよいことになる。このようにして、$a_{n+2} = p a_{n+1} + q a_{n}$ という形の３項間漸化式であればどのようなものでも一般項が表現できることになる、と思われるのだが、$\alpha = \beta$ のときにはそう簡単には問屋はおろしてくれない。

特性方程式\eqref{c0.01}は、解の範囲を複素数にまで広げれば、かならず２個の解が存在する（代数学の基本定理より）。ただし、「重複しているものを個別に数えて」２個である。ここでの特性方程式は２次方程式だから、判別式が $0$ の場合は、$\alpha = \beta$ となって重複した解になる（重根）。すると得られた等比数列 $(b_{n})$ と $(c_{n})$が同じものになってしまい、直線的に $a_{n}$ を求めることはできなくなってしまう。なので，$a_{n}$ までたどり着くには別の工夫が必要になる。その事情と工夫については、「補遺１ 重根の場合（縮退の場合）」」で検討することにする。

第２章 シフト演算子を使って解く

$\blacksquare$ シフト演算子 $\hat{L}$

$\square$ $\hat{L}$ の導入

人工的な匂いが漂う感は否めないが、数列の項にのみ作用して、その項をひとつ大きい方にずらす演算子 $\hat{L}$ \begin{align*} \hat{L}a_{n} = a_{n+1} \end{align*} というものを導入する[2-1]。さらにこの $\hat{L}$ は線型な演算子であるものとする。この線型性を、なにか別の論理から導き出せるといいのだが、そうもいかない。なので、所与の性質として仮定し、「そういうものである」と飲み込んでおく。とはいえ、その仮定の正当性がなんらかの形で保証されるとありがたいのだが、とどのつまりは話の辻褄の合い加減（理論の整合性）に頼るしかないのだろうと思う。

この線型性という性質を具体的にあらわせば、$\mu,\, \nu$ をただの数（複素数まで考慮してよい）として \begin{align*} \hat{L}(\mu a_{n} + \nu b_{n}) = \mu\hat{L}a_{n} + \nu\hat{L}b_{n} = \mu a_{n+1} + \nu b_{n+1} \end{align*} となる、という性質のことである。

$\hat{L}$ が、数列の項以外のもの（本稿では、その対象は「ただの数」しかありえないが）に作用するときは、どのような結果になるか？天下り的にその場合の作用を定義するという道もあるが、次のような説明もつけられる。数列 $(b_{n})$ の一般項が $b_{n} = a_{n} + \mu$ であるとすると、$\hat{L}$ の定義から $\hat{L}b_n = b_{n+1}$ である。これを $a_n$ であらわせば \begin{align*} \hat{L}(a_n + \mu) = a_{n+1} + \mu \;. \end{align*} また、$\hat{L}$ の線型性を尊重して \begin{align*} \hat{L}(a_n + \mu) = \hat{L}a_n + \hat{L}\mu \end{align*} という操作も認めたくなる。するとこの２つの結果から、$\hat{L}\mu = \mu$ すなわち、「ただの数に作用したときは、何も作用しない（$1$ を掛ける）」という様に取り決めれば辻褄があう。線型性に重きをおくと、$\hat{L}\mu = \mu\hat{L}$ とも記述できるので、「虚空に作用したら $1$ となる」というように考えることもできる。あるいは、一般項が $C_{n} = 1$ という定数数列を用意して $\mu = \mu C_{n}$ を考えて、$\hat{L}\mu =\hat{L}\mu C_{n} = \mu \hat{L}C_{n} = \mu C_{n+1} = \mu$ ととらえてもいい。ともあれこう約束することによって、全体として辻褄が合うようになる[2-2]。

また、これから見ていくように、代数的な演算を施したいので \begin{align*} \hat{L}^2a_{n} = \hat{L}\hat{L}a_{n} = \hat{L}(\hat{L}a_{n}) = \hat{L}a_{n+1} = a_{n+2} \end{align*} という記法とその意味合いを認めることにする。これを敷衍すれば \begin{align*} \hat{L}^n a_{k} = \overbrace{\hat{L}\hat{L}\cdots\hat{L}}^n a_{k} = \overbrace{\hat{L}(\hat{L}(\cdots\hat{L}a_{k}))\cdots)}^n = a_{k+n} \end{align*} という表記も得られる。

以上の応用の代表的な例として（$\rho,\, \tau$ もただの数） \begin{align*} (\hat{L}^2 + \rho\hat{L} + \tau)(\mu a_{n} + \nu b_{n}) &= (\hat{L}^2 + \rho\hat{L} + \tau)\mu a_{n} + (\hat{L}^2 + \rho\hat{L} + \tau)\nu b_{n} \\ &= \mu (a_{n+2} + \rho a_{n+1} + \tau a_{n}) + \nu (b_{n+2} + \rho b_{n+1} + \tau b_{n}) \end{align*} も得られる。

$\square$ 順序交換

$\hat{L}$ の多項式からなる演算子の順序交換可能性を考えてみる。といきなりいっても、その必要性はピンとこないはずである。実はこの先で、演算子を作用させる順番を変えた場合を考えることがあるのだ。したがって、作用の順番の変更すなわち順序交換の及ぼす影響を見ておくために、ここで考えてみるのである。まず \begin{align*} (\hat{L} + \rho)a_{n} = \hat{L}a_{n} + \rho a_{n} = a_{n+1} + \rho a_{n} \end{align*} であるから、 \begin{align*} (\hat{L}(\hat{L} + \rho))a_{n} = \hat{L}\{(\hat{L} + \rho)a_{n}\} = \hat{L}(a_{n+1} + \rho a_{n}) = \hat{L}a_{n+1} + \hat{L}\rho a_{n} = a_{n+2} + \rho a_{n+1} \;. \end{align*} 一方で、 \begin{align*} ((\hat{L} + \rho)\hat{L})a_{n} = (\hat{L} + \rho)\{\hat{L}a_{n}\} = (\hat{L} + \rho)a_{n+1} = a_{n+2} + \rho a_{n+1} \end{align*} であるから、結局 \begin{align*} (\hat{L} + \rho)\hat{L} = \hat{L}(\hat{L} + \rho) \end{align*} ということになる。ほぼ同様の計算を繰り返せば \begin{align*} (\hat{L} + \rho)(\hat{L} + \tau) = (\hat{L} + \tau)(\hat{L} + \rho) \end{align*} が得られることはあきらか。したがって、$\hat{L}$ の一次式からなる演算子は順序を交換しても同じ結果となることが示される（順序交換可能）。

この結果から、$\hat{L}$ についての任意の多項式 $P(\hat{L})$ と $Q(\hat{L})$ についても順序交換可能、すなわち \begin{align*} P(\hat{L})Q(\hat{L}) = Q(\hat{L})P(\hat{L}) \end{align*} であることが直ちに示せる（自明である）、と言いたいところだが、「自明」だけでですませるのは少々不親切であるとおもう（教科書を読んでいるとき、「自明」が自明でなくて何回辛い目にあったことか）。ということで、実際に証明をする際の骨格だけ書いておく：

  1. $\;$ $P(\hat{L})Q(\hat{L})$ を $\hat{L}$ の多項式同士の積とみなせば、やはり $\hat{L}$ の多項式になる。
  2. $\;$ 同様にして、$Q(\hat{L})P(\hat{L})$ も $\hat{L}$ の多項式になる。
  3. $\;$ そして、積の結果において加算は順序変更可能であるから、$\hat{L}$ の冪乗で順番を揃えることによって、$P(\hat{L})Q(\hat{L})$ も $Q(\hat{L})P(\hat{L})$ も同じ多項式になる（ここもう少しの丁寧さが必要か？）。
  4. $\;$ 同じ多項式になるのだから、数列の項に作用させた結果も同じである。
  5. $\;$ したがって、$P(\hat{L})Q(\hat{L}) = Q(\hat{L})P(\hat{L})$ つまり順序交換可能、ということになる。
（似たようなことをかつて量子力学演習の時間でやったような気がするが、忘れてしまった。もしかしたら記憶違いかもしれない。）


$\blacksquare$ ２項間漸化式であらわされる数列への応用

シフト演算子を使って３項間漸化式を考えるときの基本パーツとなる２項間漸化式について、先にその特徴をまとめておくことにする。今後の活躍が期待されるパーツである。もちろん３項以上の多項間漸化式でも有用なパーツだ。

$\square$ 等比数列での特徴

公比 $r$ の等比数列は、漸化式で書くと $a_{n+1} = r a_{n}$ であり、一般項は $a_{n} = r^n a_0$ である。シフト演算子を使ってあらわせば、まず \begin{align*} \hat{L}a_{n} = a_{n+1} = r a_{n} \end{align*} となり、これは次のような形に同値変形が可能である： \begin{align*} \hat{L}a_{n} = r a_{n} \iff (\hat{L} - r)a_{n} = 0 \;. \end{align*} 逆に言えば、 $(\hat{L} - r)a_{n} = 0$ であるのならばこれは等比数列のひとつの表現であり、$a_{n} = r^n a_0$（$a_0$ は初項）ということになる。これらを組み合わせれば、 \begin{align*} \hat{L}a_{n} = r a_{n} \iff (\hat{L} - r)a_{n} = 0 \iff (\hat{L} - r)r^n a_0 = 0 \iff r^n(\hat{L} - r)a_0 = 0 \end{align*} という形も成り立つ。

$\square$ 等差数列での特徴

もう一つの代表的な数列である等差数列（公差 $d$）では、$a_{n+1} = a_{n} + d$ であり、一般項は $a_{n} = a_0 + nd$ であるので \begin{align*} \hat{L}a_{n} = a_{n+1} = a_{n} + d \iff (\hat{L} - 1)a_{n} = d \end{align*} となる。逆に言えば、 $(\hat{L} - 1)a_{n} = d$ であるのならば、これも等差数列のひとつの表現であり、$a_{n} = a_0 + nd$ ということになる。


$\blacksquare$ ３項間漸化式であらわされる数列への応用

３項間漸化式 $a_{n+2} = p a_{n+1} + q a_{n}$ にシフト演算子 $\hat{L}$ を適用して一般項を求めてみる。$a_{n+1} = \hat{L}a_{n},\, a_{n+2} = \hat{L}^2a_{n}$ を使うと \begin{align*} a_{n+2} = p a_{n+1} + q a_{n} \iff a_{n+2} - p a_{n+1} - q a_{n} = 0 \iff \hat{L}^2 a_{n} - p\hat{L} a_{n} - q a_{n} = 0 \iff (\hat{L}^2 - p\hat{L} - q) a_{n} = 0 \end{align*} と同値変形できる。最右辺で $a_{n}$ にかかっている演算子については \begin{align*} \begin{cases} \, \alpha + \beta = p \\ \, \alpha\beta = -q \end{cases} \end{align*} となる $\alpha,\, \beta$ を使えば \begin{align*} \hat{L}^2 - p\hat{L} -q = (\hat{L} - \alpha)(\hat{L} - \beta) \end{align*} というように「因数分解」できて、2つの演算子の積としてあらわすことができる。そしてこの形式は「（３項間漸化式の）特性方程式」と全く同一のものとなっている。つまりこの $\alpha,\, \beta$ は特性方程式の解なのである。そしてこの結果から、３項間漸化式の一般項を求める問題は \begin{align*} (\hat{L}^2 - p\hat{L} - q) a_{n} = (\hat{L} - \alpha)(\hat{L} - \beta) a_{n} = 0 \end{align*} を解く問題に帰着されるのだ。


$\blacksquare$ $(\hat{L} - \alpha)(\hat{L} - \beta)a_{n} = 0$ を解く

$a_{n+2} = p a_{n+1} + q a_{n}$ は、先に見たように、シフト演算子をもちいて \begin{align} (\hat{L}^2 - p\hat{L} - q)a_{n} = 0 \iff (\hat{L} - \alpha)(\hat{L} - \beta)a_{n} = 0 \quad\text{ただし}\quad \begin{cases} \, \alpha + \beta = p \\ \, \alpha\beta = -q \end{cases} \label{s3.01} \end{align} とあらわすことが可能であった。ここでこの式に分解（のようなもの）を施して \begin{align} (\hat{L} - \alpha)b_{n} = 0 \label{s3.02} \\ (\hat{L} - \beta)c_{n} = 0 \label{s3.03} \end{align} という２つの式を考えてみると、それぞれを満たす $b_{n}$ と $c_{n}$ は、\eqref{s3.01} の解にもなっているのである。これは実際に計算してみればわかる。まず \eqref{s3.02} を満たす $b_{n}$ を \eqref{s3.01} に適用すれば（演算子の適用範囲を見やすくするために、種類の異なる括弧を細かく書くという努力をしてみた） \begin{align*} (\hat{L} - \alpha)(\hat{L} - \beta)b_{n} &= (\hat{L} - \alpha)\bigl\{(\hat{L} - \beta)b_{n}\bigr\} = (\hat{L} - \alpha)\bigl\{b_{n+1} - \beta b_{n}\bigr\} = (\hat{L} - \alpha)b_{n+1} - \beta(\hat{L} - \alpha)b_{n} = 0 \end{align*} である。最後の計算では、$(\hat{L} - \alpha)b_{n} = 0$ であるから当然 $(\hat{L} - \alpha)b_{n+1}$ も $0$ である、という $\hat{L}$ と数列ならではの事実を適用している。同様に \eqref{s3.03} を満たす $c_{n}$ を \eqref{s3.01} に適用すれば、こちらの計算は直線的で \begin{align*} (\hat{L} - \alpha)(\hat{L} - \beta)c_{n} &= (\hat{L} - \alpha)\bigl\{(\hat{L} - \beta)c_{n}\bigr\} = (\hat{L} - \alpha)0 = 0 \;. \end{align*} 以上から $b_{n}$ も $c_{n}$ も \eqref{s3.01} の解となっていることが確認できたのだ。

同様の結果は、演算子の順序交換可能性を利用して、（若干形式的に）導くこともできる。先に見たことであるが、演算子 $(\hat{L} - \alpha)$ と $(\hat{L} - \beta)$ は順序交換可能である。実際のところ、特性方程式である２次方程式の２つの解のうち、どちらを $\alpha$ にし、どちらを $\beta$ にするかはまったくの任意だから、ある意味ではこの順序交換可ということは自明なことでもある。それゆえ、まず \eqref{s3.02} からいくと、両辺の左側から $(\hat{L} - \beta)$ を作用させることにより（$\hat{L}$ のただの数への作用を思い出して） \begin{align*} (\hat{L} - \beta)\bigl\{(\hat{L} - \alpha)b_{n}\bigr\} = (\hat{L} - \beta)0 = \hat{L}0 - \beta 0 = 0 \quad\therefore\; (\hat{L} - \beta)\bigl\{(\hat{L} - \alpha)b_{n}\bigr\} = 0 \end{align*} となる。そのうえで演算子の順序を交換して \begin{align*} (\hat{L} - \alpha)(\hat{L} - \beta)b_{n} = 0 \;. \end{align*} \eqref{s3.03}から始める場合はやはりいくぶん直線的で、両辺の左側から $(\hat{L} - \alpha)$ を作用させて計算を進めれば \begin{align*} (\hat{L} - \alpha)\bigl\{(\hat{L} - \beta)c_{n}\bigr\} = (\hat{L} - \alpha)0 = \hat{L}0 - \alpha 0 = 0 \quad\therefore\; (\hat{L} - \alpha)\bigl\{(\hat{L} - \beta)c_{n}\bigr\} = 0 \quad\therefore\; (\hat{L} - \alpha)(\hat{L} - \beta)c_{n} = 0 \end{align*} となる。このようにして、$b_{n},\; c_{n}$ どちらも\eqref{s3.01}の解になっていることを示すこともできる。

$\square$ 特殊解

さて、シフト演算子 $\hat{L}$ での表式 \eqref{s3.01} であらわされる３項間漸化式のそもそもの形は \begin{align*} \eqref{s3.01} \iff a_{n+2} - (\alpha + \beta)a_{n+1} + \alpha\beta a_{n} = 0 \end{align*} というものであったのだった。そして、上で見たように、$b_{n}$ も $c_{n}$ もこの漸化式を満たすことがわかったのだった。一方で、\eqref{s3.02}、\eqref{s3.03} という２項間漸化式から、$b_{n} = \alpha^n b_0,\; c_{n} = \beta^n c_0$ という解が求まる。この２つの解が意味しているところは何なのだろうか？

$b_{n} = \alpha^n b_0$ を直接漸化式に代入してみると \begin{align*} b_{n+2} - (\alpha + \beta)b_{n+1} + \alpha\beta b_{n} = \alpha^{n+2}b_0 - (\alpha + \beta)\alpha^{n+1}b_0 + \alpha\beta \alpha^nb_0 = 0 \end{align*} となって、３項間漸化式の解であることが確認できる。$c_{n}$ についても同じである。

ならば、「３項間漸化式の解は、$b_{n} = \alpha^n b_0$ または $c_{n} = \beta^n c_0$ である」と言い切りたいところだが、なかなか問屋はそれを許してくれない。じっくりとこの $b_{n}$ をみると、$b_0$ が決まって仕舞えばあとはすべて算出できることになる。$c_{n}$ も $c_0$ さえ決まればよい。つまり、数列 $(b_{n})$ と $(c_{n})$ には勝手に選んで良い事柄が一つしかない、言い換えれば、自由度が一つしかないのである。それは、３項間漸化式が自由度を２つ持っているというそもそもの事柄に反している。なので、これら $b_{n}$ と $c_{n}$ は解であっても特別な解なのである。それゆえ、特殊解と呼ぶのである。

$\square$ 一般解

$b_{n}$ と $c_{n}$ の線型結合が \eqref{s3.01}の解になることを確認してみよう。$a_{n} = \mu b_{n} + \nu c_{n}$ と置くと、演算子の線型性から \begin{align*} (\hat{L} - \alpha)(\hat{L} - \beta)a_{n} &= (\hat{L} - \alpha)(\hat{L} - \beta)(\mu b_{n} + \nu c_{n}) = (\hat{L} - \alpha)\left\{\mu(\hat{L} - \beta)b_{n} + \nu(\hat{L} - \beta)c_{n}\right\} \\ &= (\hat{L} - \alpha)\left\{\mu b_{n+1} - \mu\beta b_{n}\right\} = \mu(\hat{L} - \alpha)b_{n+1} - \mu\beta(\hat{L} - \alpha)b_{n} \\ &= 0 \end{align*} となって、線型結合も解であることが示される。線型結合の順番を変えて、$a_{n} = \nu c_{n} + \mu b_{n}$ としても解であることは、同様な計算をすればあきらかである。ゆえに、\eqref{s3.02} と \eqref{s3.03} を個別に解いて、つまり異なる特殊解を２つ求めて、その線型結合をつくれば、それも \eqref{s3.01} の解になるのである。

特殊解は、$b_n = \alpha^n b_0,\; c_n = \beta^n c_0$ ともとまっていたから、線型結合を具体的にあらわせば \begin{align*} a_{n} = \mu b_{n} + \nu c_{n} = \mu b_0\alpha^n + \nu c_0 \beta^n \end{align*} である。この $a_{n}$ には、$\mu b_0$ と $\nu c_0$ という２つの量の任意性がある。つまり自由度が２つである。３項間漸化式においては、その自由度を初項 a_0 とその次の項 a_1 に担わせるのが常であるから、それを利用して未定の量を決めれば良い。すなわち、 \begin{align*} & a_0 = \mu b_0 + \nu c_0 \\ & a_1 = \mu b_0 \alpha + \nu c_0 \beta \end{align*} という条件を設定してそれにあてはまる $\mu b_0$ と $\nu c_0$ を導出すれば良いのだ。式が２個で未定量も２個だから、通常は解ける。 このようにして、自由度を２個含む解がもとめられる。これは、特殊ではなく一般的なものなので、一般解と呼ばれる。

特殊解の線型結合であらわされたこの具体的な形を使って、ダメ押しの確認をしておこう。$a_{n}$ に対して \begin{align*} (\hat{L} - \beta)a_{n} = a_{n+1} - \beta a_{n} = (\mu b_0\alpha^{n+1} + \nu c_0 \beta^{n+1}) - \beta(\mu b_0\alpha^n + \nu c_0 \beta^n) = \mu b_0\alpha^{n+1} - \beta\mu b_0\alpha^n = \mu b_0(\alpha - \beta)\alpha^n \end{align*} という結果から、数列 $d_{n} = (\hat{L} - \beta)a_{n}$ は、初項 $\mu b_0(\alpha - \beta)$ で公比 $\alpha$ の等比数列であることがわかる。$\alpha$ の等比数列なのだから $(\hat{L} - \alpha)d_{n} = 0$ である。つまり、 \begin{align*} (\hat{L} - \alpha)d_{n} = (\hat{L} - \alpha)(\hat{L} - \beta)a_{n} = 0 \end{align*} が導かれるし、さらに計算を進めれば \begin{align*} (\hat{L} - \alpha)(\hat{L} - \beta)a_{n} = (\hat{L} - \alpha)(a_{n+1} - \beta a_{n}) = a_{n+2} - \alpha a_{n+1} - \beta a_{n+1} + \alpha\beta a_{n} = a_{n+2} - (\alpha + \beta)a_{n+1} + \alpha\beta a_{n} = 0 \end{align*} というそもそもの３項間漸化式が導かれる。当然のことである。

ここまでの議論は \begin{align*} (\hat{L}^2 - p\hat{L} - q) = (\hat{L} - \alpha)(\hat{L} - \beta) \quad\text{ただし}\quad \alpha \neq \beta \end{align*} である場合の議論である。ところで、２次方程式には重根というものが存在するので、 \begin{align*} (\hat{L}^2 - p\hat{L} - q) = (\hat{L} - \alpha)^2 \end{align*} となる場合もありうる。これはなかなか一筋縄では行かないので、やはり「補遺１ 重根の場合（縮退の場合）」のところで別途考えることにしておく。

上で述べた、線型結合が解になるという事実をすこしだけ一般化しておいてみようと思う。示したいことは、

線型性をもつ２つの演算子を $\hat{A}$ と $\hat{B}$ があり、$\hat{A}\hat{B}$ は順序交換可能、すなわち $\hat{A}\hat{B} = \hat{B}\hat{A}$ であるとする。このとき、 $\begin{cases} \hat{A}\vec{x} = \vec{0} \\ \hat{B}\vec{y} = \vec{0} \end{cases} $ が成り立つのであれば、$\vec{x}$ と $\vec{y}$ は $\hat{A}\hat{B}\vec{z} = \vec{0}$ の解になっており、またそれら $\vec{x}$ と $\vec{y}$ の線型結合も解、すなわち $\hat{A}\hat{B}(\mu\vec{x} + \nu\vec{y}) = \vec{0}$ が成り立つ。
ということである。淡々と計算をすすめればよい。$\hat{A}\hat{B} = \hat{B}\hat{A}$ だから \begin{align*} \hat{A}\hat{B}\vec{x} = \hat{B}\hat{A}\vec{x} = \hat{B}(\hat{A}\vec{x}) = \vec{0} \end{align*} である。そしてまた \begin{align*} \hat{A}\hat{B}\vec{y} = \hat{A}(\hat{B}\vec{y}) = \vec{0} \end{align*} であるから、$\vec{x},\, \vec{y}$ ともに $\hat{A}\hat{B}\vec{z} = \vec{0}$ の解である。次に \begin{align*} \hat{A}\hat{B}(\mu\vec{x} + \nu\vec{y}) = \hat{A}\hat{B}\mu\vec{x} + \hat{A}\hat{B}\nu\vec{y} = \mu\hat{A}\hat{B}\vec{x} + \nu\hat{A}\hat{B}\vec{y} = \mu\hat{B}\hat{A}\vec{x} + \nu\hat{A}\hat{B}\vec{y} = \vec{0} \end{align*} であるから、$\vec{x}$ と $\vec{y}$ の線型結合も $\hat{A}\hat{B}\vec{z} = \vec{0}$ の解である。この理路の肝は、$\hat{A}\hat{B} = \hat{B}\hat{A}$ という順序交換が可能であることに尽きる。

往々にして、上記の $\vec{x}$ や $\vec{y}$ を「特殊解」、その線型結合 $(\mu\vec{x} + \nu\vec{y})$ を一般解と言ったりすることがある。また、この形式を「重ね合わせ（の原理）」と呼んだりもする。微分方程式の世界で顕著な言葉づかいである。


第２章の脚註

[2-1]  筆者はこの演算子 $\hat{L}$ の存在を、「ふたりの微積分（スティーヴン・ストロガッツ著、南條郁子訳）」から学んだ。
[2-2]  演算子ですぐに思いつくポピュラーなものは微分演算子 $\hat{D} = d/dx$ だ。この微分演算子は、$\hat{D}(\alpha f(x)) = \alpha \hat{D}f(x)$ という線型性はおなじように成り立つのだけれど、ただの数に作用すると $\hat{D}\alpha = 0$ となっていて、$\hat{L}$ のふるまいとはちょっと違っている。屁理屈をいえば、こちらは \begin{align*} \hat{D}(\alpha f(x)) = (\hat{D}\alpha)f(x) + \alpha\hat{D}f(x) = \alpha\hat{D}f(x) \end{align*} というように、積の演算法則を成立させてそのうえで線型性も確保する、という辻褄の上で $\hat{D}\alpha = 0$ が取り決められているといえよう。

第３章 行列の対角化を使って解く

$\blacksquare$ 行列による表現

３項間漸化式 $a_{n+2} = p a_{n+1} + q a_{n}$ を、ひと工夫入れて行列を使って表現すると \begin{align*} \begin{pmatrix} a_{n+2} \\ a_{n+1} \end{pmatrix} = \begin{pmatrix} p a_{n+1} + q a_{n} \\ a_{n+1} \end{pmatrix} = \begin{pmatrix} p & q \\ 1 & 0 \end{pmatrix} \begin{pmatrix} a_{n+1} \\ a_{n} \end{pmatrix} \end{align*} とあらわすことができる（行列の２行目がそのひと工夫である）。これを順次展開していけば \begin{align*} \begin{pmatrix} a_{n+2} \\ a_{n+1} \end{pmatrix} = \begin{pmatrix} p & q \\ 1 & 0 \end{pmatrix} \begin{pmatrix} a_{n+1} \\ a_{n} \end{pmatrix} = \begin{pmatrix} p & q \\ 1 & 0 \end{pmatrix} \begin{pmatrix} p & q \\ 1 & 0 \end{pmatrix} \begin{pmatrix} a_{n} \\ a_{n-1} \end{pmatrix} = \cdots = \begin{pmatrix} p & q \\ 1 & 0 \end{pmatrix} \begin{pmatrix} p & q \\ 1 & 0 \end{pmatrix} \cdots \begin{pmatrix} p & q \\ 1 & 0 \end{pmatrix} \begin{pmatrix} a_1 \\ a_0 \end{pmatrix} \end{align*} となるから結果として \begin{align} \begin{pmatrix} a_{n+2} \\ a_{n+1} \end{pmatrix} = \begin{pmatrix} p & q \\ 1 & 0 \end{pmatrix}^{n+1} \begin{pmatrix} a_1 \\ a_0 \end{pmatrix} \label{m0.01} \end{align} となる。したがって、$p,\, q$ がどのような数であっても、初項 $a_0$ と 第２項 $a_1$ が決まりさえすれば、一般項はこの形で与えられる[3-1]。行列の計算という面倒さはあるけれども。

フィボナッチ数列の漸化式は $a_{n+2} = a_{n+1} + a_{n}$ であるから、$p = 1,\, q = 1$ となり、また初項は $a_0 = 0,\, a_1 = 1$ だから \begin{align*} \begin{pmatrix} a_{n+2} \\ a_{n+1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n+1} \begin{pmatrix} 1 \\ 0 \end{pmatrix} \end{align*} が一般項となる。

$a_{n+2} = \sqrt{2}a_{n+1} + i a_n$ （$i$ は虚数単位）という漸化式で与えられる数列の一般項は、$p = \sqrt{2},\, q = i$ の場合だから \begin{align*} \begin{pmatrix} a_{n+2} \\ a_{n+1} \end{pmatrix} = \begin{pmatrix} \sqrt{2} & i \\ 1 & 0 \end{pmatrix}^{n+1} \begin{pmatrix} a_1 \\ a_0 \end{pmatrix} \end{align*} となる。


$\blacksquare$ 対角行列による冪乗の計算

行列の形式での一般項は上のようにして求まったが、やはり行列計算は面倒なものである。もうすこし計算が簡単になる一般項の表現形式ないものだろうかと頭を使ってみたい。

そういえば、正方行列（今その次元を $d$ とする。すなわち $d \times d$ の行列である）の世界では \begin{align*} \begin{pmatrix} \lambda_1 & 0 & \cdots & 0 \\ 0 & \lambda_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \lambda_d \end{pmatrix}^k = \begin{pmatrix} (\lambda_1)^k & 0 & \cdots & 0 \\ 0 & (\lambda_2)^k & \cdots & 0 \\ \vdots & \vdots & \ddots &\vdots \\ 0 & 0 & \cdots & (\lambda_d)^k \end{pmatrix} \end{align*} というように、対角行列の冪乗は非常に計算が楽になるのであった（実際に行列の掛け算を実行すればすぐに確認できる。念の為に断っておけば、$k$ は正の整数。$k=0$ のときは、単位行列 $\mat{E}$（$\mat{I}$ と書くこともある）になることは $(\lambda_i)^0 = 1$ であること[3-2]からあきらかである）。それゆえ、\eqref{m0.01}の行列 $ \begin{pmatrix} p & q \\ 1 & 0 \end{pmatrix} $ から何らかの方法で対角行列が作り出せれば、一般項の形式も簡単に計算できるものになるのではないかと予想できる。


$\blacksquare$ 固有値方程式による対角化

ここからは、数列の漸化式と一般項からいったん離れて、行列の一般論の力を借りて「固有値方程式からの行列の対角化」を導き出してみる。なお、以下に出てくる行列は、特段ことわらない限り全て $d$ 次元の正方行列であり、列ベクトルも $d$ 次元の列ベクトルであるとする。さらに $\mat{E}$ は単位行列をあらわすものとする。

行列 $\mat{A}$ から対角行列を導き出そうというのがこれからの目的であるが、そもそもは $\mat{A}$ の冪乗を計算することが本題なのだから、それに見合った方法を採用しなくてはならないだろう。たとえば何らかの行列 $\mat{B}$ を加えることによって偶然にも対角行列 $\mat{D}$ が求まったとしよう（こういう $\mat{B}$ は対角成分以外は $\mat{A}$ の成分の符号変えたものにすればいいのだから、求めることは造作もない）。すなわち $ \mat{A} + \mat{B} = \mat{D} $ であったとして、これを $k$ 乗してみると \begin{align*} (\mat{A} + \mat{B})^k = (\mat{A} + \mat{B})(\mat{A} + \mat{B})\cdots(\mat{A} + \mat{B}) = \mat{D}^k \end{align*} となり、確かに対角行列 $\mat{D}$ の $k$ 乗の方は簡単に計算できるだろうが、$\mat{A}$ の $k$ 乗が簡単に計算できるようにはみえない。それに $\vec{B}$ の $k$ 乗なども含めて面倒なものが増えてくる。

また、$\mat{B}$ を掛けることによって対角行列となった場合、すなわち $ \mat{A}\mat{B} = \mat{D} $ というようなとき（たとえば $\mat{A}$ の逆行列が存在するとする。$c$ を定数として $\mat{B} = c\mat{A}^{-1}$ というものを考えれば $\mat{A}\mat{B} = \mat{A} c \mat{A}^{-1} = c \mat{E}$ でこれは十分立派な対角行列だ）、これを $k$ 乗してみると \begin{align*} (\mat{A}\mat{B})^k = \mat{A}\mat{B}\mat{A}\mat{B}\cdots\mat{A}\mat{B} = \mat{D}^k \end{align*} となって、やはり $\mat{A}$ の $k$ 乗が簡単に計算できるようにはみえない。

ここで、ひとつの特殊な場合を考える。ある行列 $\mat{P}$ があって \begin{align} \mat{P}^{-1}\mat{A}\mat{P} = \mat{D} \label{m2.01} \end{align} という計算によって（当然のごとく、$\mat{P}^{-1}$ は $\mat{P}$ の逆行列）対角行列 $\mat{D}$ が求まったとする。すると \begin{align*} & \mat{D}^2 = (\mat{P}^{-1}\mat{A}\mat{P})(\mat{P}^{-1}\mat{A}\mat{P}) = \mat{P}^{-1}\mat{A}\mat{P}\mat{P}^{-1}\mat{A}\mat{P} = \mat{P}^{-1}\mat{A}^2\mat{P} \\ & \quad\cdots \\ & \mat{D}^k = \mat{P}^{-1}\mat{A}^k\mat{P} \end{align*} となる。この結果に対して適切に両辺に $\mat{P}$ と $\mat{P}^{-1}$ を作用させれば \begin{align*} \mat{A}^k = \mat{P}\mat{D}^k\mat{P}^{-1} \end{align*} となって、求める行列 $\mat{A}$ の $k$ 乗が導出できる。$\mat{D}^k$ の計算は簡単だったので、$\mat{P}\mat{D}^k\mat{P}^{-1}$ もそれほど手間ではないはずだ。このようなおあつらえむきの 行列 $P$（と $P^{-1}$）が求まれば万々歳であるが、はて、どのようにして求めれば良いのだろうか。

\eqref{m2.01}の両辺に左側から $\mat{P}$ をかけると \begin{align} \mat{P}\mat{P}^{-1}\mat{A}\mat{P} = \mat{P}\mat{D} \quad\therefore\; \mat{A}\mat{P} = \mat{P}\mat{D} \;. \label{m2.02} \end{align} $\mat{D}$ は対角行列であると仮定したのだから、 \begin{align*} \mat{D} = \begin{pmatrix} \lambda_1 & 0 & \cdots & 0 \\ 0 & \lambda_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \lambda_d \end{pmatrix} \end{align*} とあらわせる。次に、今後のために、$\mat{P}$ を列ベクトルに分解してあらわす。そのためにまず \begin{align*} \vec{v}_1 = \begin{pmatrix} v_{11} \\ v_{21} \\ \vdots \\ v_{d1} \end{pmatrix} \;, \quad \vec{v}_2 = \begin{pmatrix} v_{12} \\ v_{22} \\ \vdots \\ v_{d2} \end{pmatrix} \;, \;\cdots\;, \vec{v}_d = \begin{pmatrix} v_{1d} \\ v_{2d} \\ \vdots \\ v_{dd} \end{pmatrix} \end{align*} とサフィックスにすこし工夫をした列ベクトルの群れ $\vec{v}_i$ を用意して、 \begin{align*} \mat{P} = \begin{pmatrix} v_{11} & v_{12} & \cdots & v_{1d} \\ v_{21} & v_{22} & \cdots & v_{2d} \\ \vdots & \vdots & \ddots & \vdots \\ v_{d1} & v_{d2} & \cdots & v_{dd} \end{pmatrix} = \begin{pmatrix} \vec{v}_1 & \vec{v}_2 & \cdots & \vec{v}_d \end{pmatrix} \end{align*} とあらわす。これを利用すれば \begin{align*} & \mat{A}\mat{P} = \mat{A} \begin{pmatrix}\vec{v}_1 & \vec{v}_2 & \cdots & \vec{v}_d \end{pmatrix} = \begin{pmatrix} \mat{A}\vec{v}_1 & \mat{A}\vec{v}_2 & \cdots & \mat{A}\vec{v}_d \end{pmatrix} \\ &\mat{P}\mat{D} = \begin{pmatrix}\vec{v}_1 & \vec{v}_2 & \cdots & \vec{v}_d \end{pmatrix} \mat{D} = \begin{pmatrix} \lambda_1\vec{v}_1 & \lambda_2\vec{v}_2 & \cdots & \lambda_d\vec{v}_d \end{pmatrix} \end{align*} となるので、\eqref{m2.02} は \begin{align} \begin{cases} \, \mat{A}\vec{v}_1 = \lambda_1\vec{v}_1 \\ \, \mat{A}\vec{v}_2 = \lambda_2\vec{v}_2 \\ \quad\cdots \\ \, \mat{A}\vec{v}_d = \lambda_d\vec{v}_d \end{cases} \label{m2.03} \end{align} ということをあらわしていることになる。これは、行列 $\mat{A}$ の固有値方程式と呼ばれる $\mat{A}\vec{v} = \lambda\vec{v}$ の個別の結果にほかならない。そして $\lambda_i$ は固有値と呼ばれるもののひとつであり、$\vec{v}_i$ は固有値 $\lambda_i$ に対応する固有ベクトルと呼ばれるものである（$i = 1, 2, \ldots, d$）。

行列を列ベクトルであらわした場合のこのような計算に普段あまり馴染みのない筆者のような者は、なかなかすんなりとは納得がいかない。ここで、$2 \times 2$ の行列でこの計算を具体的に確認してみることにする。 \begin{align*} \mat{A} = \begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix} \;, \quad \vec{v}_1 = \begin{pmatrix} v_{11} \\ v_{21} \end{pmatrix} \;, \quad \vec{v}_2 = \begin{pmatrix} v_{12} \\ v_{22} \end{pmatrix} \end{align*} とする。これらから \begin{align*} \mat{A}\vec{v}_1 = \begin{pmatrix} a_{11}v_{11} + a_{12}v_{21} \\ a_{21}v_{11} + a_{22}v_{21} \end{pmatrix} \;,\quad \mat{A}\vec{v}_2 = \begin{pmatrix} a_{11}v_{21} + a_{12}v_{22} \\ a_{21}v_{21} + a_{22}v_{22} \end{pmatrix} \end{align*} という結果がもとまる。またさらに $ \mat{P} = \begin{pmatrix} \vec{v}_1 & \vec{v}_2 \end{pmatrix} = \begin{pmatrix} v_{11} & v_{12} \\ v_{21} & v_{22} \end{pmatrix} $ とあらわせるのだから、 \begin{align*} \mat{A}\mat{P} = \begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix} \begin{pmatrix} v_{11} & v_{12} \\ v_{21} & v_{22} \end{pmatrix} = \begin{pmatrix} a_{11}v_{11} + a_{12}v_{21} & a_{11}v_{12} + a_{12}v_{22} \\ a_{21}v_{11} + a_{22}v_{21} & a_{21}v_{12} + a_{22}v_{22} \end{pmatrix} = \begin{pmatrix} \mat{A}\vec{v}_1 & \mat{A}\vec{v}_2 \end{pmatrix} \end{align*} となる。対角行列 $\mat{D}$ を $ \mat{D} = \begin{pmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{pmatrix} $ とあらわしておけば \begin{align*} \mat{P}\mat{D} = \begin{pmatrix} v_{11} & v_{12} \\ v_{21} & v_{22} \end{pmatrix} \begin{pmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{pmatrix} = \begin{pmatrix} \lambda_1 v_{11} & \lambda_2 v_{12} \\ \lambda_1 v_{21} & \lambda_2 v_{22} \end{pmatrix} = \begin{pmatrix} \lambda_1 \vec{v}_1 & \lambda_2 \vec{v}_2 \end{pmatrix} \;. \end{align*} それゆえ \begin{align*} \mat{A}\mat{P} = \mat{P}\mat{D} \iff \begin{cases} \, \mat{A}\vec{v}_1 = \lambda_1 \vec{v}_1 \\ \, \mat{A}\vec{v}_2 = \lambda_2 \vec{v}_2 \\ \end{cases} \end{align*} となるのである。

したがってこの理路を逆にたどれば

  1. $\;$ $\mat{A}\vec{v} = \lambda\vec{v}$ という固有値方程式をたてて、
  2. $\;$ 固有値 $\lambda_i$ と対応する固有ベクトル $\vec{v}_i$ をもとめることによって、
  3. $\;$ $\mat{P} = \begin{pmatrix} \vec{v}_1 & \vec{v}_2 & \cdots & \vec{v}_d \end{pmatrix}$ が得られ（固有ベクトルからなる行列）、
  4. $\;$ $\mat{P}^{-1}\mat{A}\mat{P} = \mat{D} = \begin{pmatrix} \lambda_1 & 0 & \cdots & 0 \\ 0 & \lambda_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \lambda_d \end{pmatrix} $ という対角成分が固有値の対角行列も得られる
ということになる。問題の照準は、固有値方程式の解法とその解の性質に移ったのだ。


$\blacksquare$ 固有値方程式の解法

この節を書くのに悩みが少々。固有値方程式の説明のためには、行列論、行列式論の定理のお世話にならざるを得ないのだが、それらひとつひとつを証明しようとすると、ことはそれほど簡単なものではなく、かなり大掛かりなものになることがわかった。それゆえ、本題が見えにくくなってしまうこともわかった。といって全て天下り的に「この定理を認めよ」というのも、なんだかやるせない気がしてしまう。でもまあそれもしょうがないか。「きちんとした教科書にあたって確かめてください」と言い逃れをすることで許してもらうことにしよう。

ことばを再確認しておく。まず $\mat{A},\; \mat{P},\; \mat{D}$ などであらわされる行列は $d$ 次の正方行列あるとする。そして $\mat{E}$ を $d$ 次の単位行列をあらわすものとする。そして、 \begin{align*} \mat{A}\vec{v} = \lambda\vec{v} \end{align*} を固有値方程式といい、ここにあらわれている $\lambda$ を固有値、$\vec{v}$ を固有ベクトルと呼ぶ。一般に固有値は複数存在するので、それをあらわに示したいときは $\lambda_i$ のようにサフイックスをつける。そのうえで、個別の固有値 $\lambda_i$ に対応する固有ベクトルを $\vec{v}_i$ と記す。あわせればすなわち、$\mat{A}\vec{v}_i = \lambda_i\vec{v}_i$ となる。

ここからは、種々の性質と定理の記述に向かう。まず固有ベクトルの任意性について。固有値 $\lambda$ の固有ベクトルを $\vec{v}$ とすると、$\vec{v}$ の定数倍も固有値 $\lambda$ の固有ベクトルである。つまり、固有ベクトルには定数倍の曖昧性が残るのである。なぜならば、$c$ を定数として $\vec{v}^\prime = c\vec{v}$ とすると、$\mat{A}$ の線型性から定数倍を施す因子は前に出せて、 \begin{align*} \mat{A}\vec{v}^\prime = \mat{A}c\vec{v} = c\mat{A}\vec{v} = c\lambda\vec{v} = \lambda c\vec{v} = \lambda\vec{v}^\prime \end{align*} となって、$\vec{v}$ も $c\vec{v}$ も $\lambda$ に対する固有ベクトルであることがわかるからである。つまり


=== 定理 ===
固有値方程式 $\mat{A}\vec{v} = \lambda\vec{v}$ を満たす固有ベクトル $\vec{v}$ の定数倍 $c\vec{v}$ も、固有値 $\lambda$ に対する固有ベクトルである。


さて一方で、固有値方程式は \begin{align} \mat{A}\vec{v} = \lambda\vec{v} \iff (\mat{A} - \lambda\mat{E})\vec{v} = \vec{0} \label{m3.01} \end{align} と変形できる。そして $\vec{v} = \vec{0}$ が解であることはあきらか。これを「自明な解」という。それ以外の解、つまり非自明な解、が存在するための必要十分条件として次の定理がある：


=== 定理 ===
固有値方程式 $\mat{A}\vec{v} = \lambda\vec{v}$ において \begin{align*} \text{$\vec{v} = \vec{0}$ 以外の非自明な解を持つ} \iff \det(\mat{A} - \lambda\mat{E}) = 0 \end{align*} という同値関係（必要十分関係）が成立する。


この行列式（determinant）を使ってあらわされている右側の方程式を「特性方程式、または、固有方程式」と呼ぶ（これにも「特性方程式という名前がついている）。この定理の意味を再確認しよう。仮に、$\mat{A} - \lambda\mat{E}$ が逆行列を持つとすると、その逆行列を \eqref{m3.01} に左から作用させることができて、結果 $\vec{v} = \vec{0}$ 以外の解が存在しなくなってしまう。なので、$\vec{v} = \vec{0}$ 以外の解が存在するためには逆行列を持ってはいけない、すなわち、行列式が $0$ でなければならない、ということなのである（ついでにいえば、正則であってはならない）。

この特性方程式は、あきらかに、$\lambda$ についての $d$ 次の方程式である。またこの形から、行列 $\mat{A} - \lambda\mat{E}$ は正則[3-3]ではない、逆行列を持たない、という言い方もできる。さらに特性方程式は $\lambda$ の $d$ 次の方程式であるから、代数学の基本定理により、複素数の範囲で $d$ 個の解を持つ（重複している場合には、重複分を勘定に入れる）。したがって、特性方程式の解のひとつを $\lambda_i$ とすると $\lambda_i$ に対応する固有ベクトル $\vec{v}$ は $\mat{A}\vec{v} = \lambda_i\vec{v}$（または $(\mat{A} - \lambda_i\mat{E})\vec{v} = \vec{0}$）を解けば得られるが、上で見たようにその解には定数倍の任意性がある。そのなかで一番わかりやすい（「簡単な」と言った方が良いかもしれない）固有ベクトルを $ \vec{v}_i = \begin{pmatrix} v_{1i} \\ v_{2i} \\ \vdots \\ v_{di} \end{pmatrix} $ とあらわすことにする。「一番わかりやすい」という恣意的な言い方になっているが、どれも固有値方程式の解なのであるから、これは恣意的で構わない。

特性方程式の解となる $d$ 個の $\lambda$ がすべて異なるとき、「固有値は縮退していない」という。そして縮退していないときには次の定理がなりたつ：


=== 定理 ===
固有値方程式の固有値が縮退していない、つまり、$d$ 個の固有値が全て異なっているときには、それぞれの固有値に対応する $d$ 個の固有ベクトルは線型独立[3-4]である（この【逆】つまり、$d$ 個の固有ベクトルが線型独立であるならば、$d$ この固有値はすべて異なる（縮退していない）、とは言えないだろうか？言えそうな気がするのだがいまひとつ自信がない）。


$\vec{v}_i\, (i=1,2,\ldots,d)$ が線型独立な $d$ 個の列ベクトルであるとする。そのときこの列ベクトルから作られる行列 $ \mat{P} = \begin{pmatrix} \vec{v}_1 & \vec{v}_2 & \cdots & \vec{v}_d \end{pmatrix} $ を考える。この $\mat{P}$ については


=== 定理 ===
上のように線型独立な（異なる）固有ベクトルを使って定義された行列 $\mat{P}$ は、逆行列をもつ（同じことだが、正則である、$\det{\mat{P}} \neq 0$）。


がなりたつ。さて $\vec{v}_i$ は固有値 $\lambda_i$ に対する固有ベクトルだから \begin{align*} \mat{A}\mat{P} = \mat{A} \begin{pmatrix} \vec{v}_1 & \vec{v}_2 & \cdots & \vec{v}_d \end{pmatrix} = \begin{pmatrix} \mat{A}\vec{v}_1 & \mat{A}\vec{v}_2 & \cdots & \mat{A}\vec{v}_d \end{pmatrix} = \begin{pmatrix} \lambda_1\vec{v}_1 & \lambda_2\vec{v}_2 & \cdots & \lambda_d\vec{v}_d \end{pmatrix} = \mat{P} \begin{pmatrix} \lambda_1 & 0 & \cdots & 0 \\ 0 & \lambda_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \lambda_d \end{pmatrix} \end{align*} となる（固有値と固有ベクトルの並び方の対応に留意）。ここで生成された対角行列を $\mat{D}$ と書きあらわす。先に述べた定理より、逆行列 $\mat{P}^{-1}$ が存在することがわかっているから、上の結果の式において左側から $\mat{P}^{-1}$ をかけると \begin{align*} \mat{P}^{-1}\mat{A}\mat{P} = \mat{P}^{-1}\mat{P}\mat{D} \quad\therefore\; \mat{P}^{-1}\mat{A}\mat{P} = \mat{D} \end{align*} となって、$\mat{A}$ と $\mat{P}$ から対角行列を生成することができる。これを、$\mat{A}$ の対角化という。

この結果から、 \begin{align*} \mat{P}^{-1}\mat{A}\mat{P} = \mat{D} \iff \mat{A} = \mat{P}\mat{D}\mat{P}^{-1} \end{align*} となるから、$\mat{A}$ の冪乗は \begin{align*} \mat{A}^n = (\mat{P}\mat{D}\mat{P}^{-1})(\mat{P}\mat{D}\mat{P}^{-1})\cdots(\mat{P}\mat{D}\mat{P}^{-1}) = (\mat{P}\mat{D}^2\mat{P}^{-1})(\mat{P}\mat{D}\mat{P}^{-1})\cdots(\mat{P}\mat{D}\mat{P}^{-1}) = \mat{P}\mat{D}^n\mat{P}^{-1} \end{align*} ということになる。$\mat{D}$ は対角行列であるから、この計算はそんなに手間ではない。

ここまで述べてきた $\mat{A}$ が対角化されるまでの手順を、定理のかたちに集約すると、次のようになる：


=== 定理 ===
$d$ 次の正方行列 $\mat{A}$ が $d$ 個の線型独立な固有ベクトルを持つ。$\implies$ $\mat{A}$ は対角化可能である。



$\blacksquare$ ３項間漸化式への応用

３項間漸化式 $a_{n+2} = p a_{n+1} + q a_{n}$ にもどろう。\eqref{m0.01}の行列を $\mat{A}$ と書けば \begin{align} \begin{pmatrix} a_{n+2} \\ a_{n+1} \end{pmatrix} = \begin{pmatrix} p & q \\ 1 & 0 \end{pmatrix}^{n+1} \begin{pmatrix} a_1 \\ a_0 \end{pmatrix} = \mat{A}^{n+1} \begin{pmatrix} a_1 \\ a_0 \end{pmatrix} \label{m4.01} \end{align} となる。固有値を求めるために、特性方程式を具体的に計算すると \begin{align*} \det(\mat{A} - \lambda\mat{E}) = \det\left\{ \begin{pmatrix} p & q \\ 1 & 0 \end{pmatrix} - \begin{pmatrix} \lambda & 0 \\ 0 & \lambda \end{pmatrix} \right\} = \det\left\{ \begin{pmatrix} p - \lambda & q \\ 1 & -\lambda \end{pmatrix} \right\} = \lambda^2 - p\lambda - q = 0 \end{align*} となって、今まで見てきたものと同じ２次方程式になっている（なのですべてを特性方程式と言いつのるのである）。ここで

  1. この解を $\lambda_1,\, \lambda_2$ とし、
  2. 重根をもたない、つまり、縮退していないとして、
  3. $\lambda_1,\, \lambda_2$ それぞれの固有ベクトルを $\vec{v}_1,\, \vec{v}_2$ とし、
  4. $\mat{P} = \begin{pmatrix} \vec{v}_1 & \vec{v}_2 \end{pmatrix}$ とする
ことによって、$\mat{A}$ を対角化した行列 \begin{align*} \mat{P}^{-1}\mat{A}\mat{P} = \mat{D} = \begin{pmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{pmatrix} \end{align*} が得られる。それをもとに \begin{align*} \mat{A}^n = \mat{P}\mat{D}^n\mat{P}^{-1} = \mat{P} \begin{pmatrix} (\lambda_1)^n & 0 \\ 0 & (\lambda_2)^n \end{pmatrix} \mat{P}^{-1} \end{align*} が計算できるので、\eqref{m4.01}に適用して一般項を求めれば良い。固有値が縮退しているときの扱いについては、「補遺１ 重根の場合（縮退の場合）」のところでふれる。


第３章の脚註

[3-1]  自然数に律儀に向き合い、初項を $a_1$、第２項を $a_2$ とするのならば、 $ \begin{pmatrix} a_{n+2} \\ a_{n+1} \end{pmatrix} = \begin{pmatrix} p & q \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} a_2 \\ a_1 \end{pmatrix} $ である。
[3-2]  「$(\lambda_i)^0 = 1$ である」と言い切ると何か他の概念から導出されてくるもののように思えるが、実のところこれは指数表記の拡張（自然数から整数にまで、ひいては実数、複素数にまで）において整合性をとるための定義であると考えた方がいい。すなわち「数の $0$ 乗は１と定める。」
[3-3]  次の様に全て同値な述語である（ほぼ用語の定義に過ぎない）： \begin{align*} \mat{A} \text{が正則である。} \iff \det(\mat{A}) \neq 0 \iff \mat{A} \text{は逆行列 $\mat{A}^{-1}$ を持つ。} \end{align*}
[3-4]  線型独立ということがらを、馴染み深い３次元ユークリッド空間の直行座標を題材にして述べてみよう。各直行座標軸の単位ベクトルを $\hat{\vec{x}},\, \hat{\vec{y}},\, \hat{\vec{z}}$ とする。これら３個のベクトルが線型独立である、ということは、この３個のベクトルのうちどれひとつとして他の２個のベクトルの線型結合ではあらわせない（たとえば、$\hat{\vec{z}} = \mu \hat{\vec{x}} + \nu \hat{\vec{y}}$ となるような $\mu,\, \nu$ は存在しない、ということである。これとまったく同値な言い方として、次のものがよく使われる。 \begin{align*} \mu\hat{\vec{x}} + \nu\hat{\vec{y}} + \xi\hat{\vec{z}} = \vec{0} \iff \mu = \nu = \xi = 0 \;. \end{align*}

エクササイズ１： $a_{n+2} = 5 a_{n+1} - 6 a_{n}$ の一般項を求める

$\blacksquare$ 特性方程式を使って

\begin{align*} a_{n+2} = 5 a_{n+1} - 6 a_{n} \iff a_{n+2} - 5 a_{n+1} + 6 a_{n} = 0 \end{align*} であるから、この３項間漸化式の特性方程式をとけば、 \begin{align*} x^2 - 5x + 6 = (x - 2)(x - 3) = 0 \quad\therefore\; \alpha = 2, \, \beta = 3 \end{align*} となる（$\alpha$ と $\beta$ が逆でも良いことをことわるべきだろうか？）。したがって、 \begin{align*} & a_{n+1} - \alpha a_{n} = \beta^n(a_1 - \alpha a_0) \quad\text{より}\quad a_{n+1} - 2a_{n} = 3^n(a_1 - 2a_0) \;,\\ & a_{n+1} - \beta a_{n} = \alpha^n(a_1 - \beta a_0) \quad\text{より}\quad a_{n+1} - 3a_{n} = 2^n(a_1 - 3a_0) \;. \end{align*} 上の式から下の式をひいて $a_{n+1}$ を消去すると \begin{align*} a_n = 3^n(a_1 - 2a_0) - 2^n(a_1 - 3a_0) \;. \end{align*} あとは $a_0$ と $a_1$ 次第である。たとえば \begin{alignat*}{2} & a_0 = 0, a_1 =1 \quad\text{のときは}\quad a_n = 3^n - 2^n & &\quad\text{i.e.}\quad (a_n) = (0, 1, 5, 19, 65, 211, \ldots) \\ & a_0 = 1, a_1 =1 \quad\text{のときは}\quad a_n = -3^n + 2^{n+1} & &\quad\text{i.e.}\quad (a_n) = (1, 1, -1, -11, -49, -179, \ldots) \end{alignat*} というようになる。


$\blacksquare$ シフト演算子 $\hat{L}$ を使って

漸化式 $a_{n+2} - 5 a_{n+1} + 6 a_{n} = 0$ はシフト演算子 $\hat{L}$ を使うと \begin{align*} \hat{L}^2a_{n} - 5\hat{L}a_{n} + 6 a_{n} = (\hat{L}^2 - 5\hat{L} + 6)a_{n} = (\hat{L} - 3)(\hat{L} - 2)a_{n} = 0 \end{align*} とあらわされる。これより \begin{align*} & (\hat{L} - 3)b_{n} = 0 \\ & (\hat{L} - 2)c_{n} = 0 \end{align*} をみたす公比 $3$ の等比数列の一般項 $b_{n}$ と、公比 $2$ の等比数列の一般項 $c_{n}$ が特殊解である。それゆえ、一般項 $a_{n}$ は、$b_{n}$ と $c_{n}$ の線型結合となるので \begin{align*} a_{n} = \mu 3^n + \nu 2^n \end{align*} となる。

$\mu$ と $\nu$ は $a_0$ と $a_1$ から決まる。$a_0 = 0, a_1 = 1$ という条件のときには \begin{align*} \begin{cases} \, a_0 = \mu + \nu = 0 \\ \, a_1 = 3\mu + 2\nu = 1 \end{cases} \quad\therefore\; \begin{cases} \, \mu = 1 \\ \, \nu = -1 \end{cases} \quad\therefore\; a_{n} = 3^n - 2^n \;. \end{align*} $a_0 = 1, a_1 = 1$ という場合には \begin{align*} \begin{cases} \, a_0 = \mu + \nu = 1 \\ \, a_1 = 3\mu + 2\nu = 1 \end{cases} \quad\therefore\; \begin{cases} \, \mu = -1 \\ \, \nu = 2 \end{cases} \quad\therefore\; a_{n} = -3^n + 2^{n+1} \;. \end{align*} 当然であるが、特性方程式を使って求めた結果と同じである。


$\blacksquare$ 行列の対角化を使って

漸化式 $a_{n+2} - 5 a_{n+1} + 6 a_{n} = 0$ を行列であらわすと \begin{align} \begin{pmatrix} a_{n+2} \\ a_{n+1} \end{pmatrix} = \begin{pmatrix} 5 & -6 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} a_{n+1} \\ a_{n} \end{pmatrix} = \cdots = \begin{pmatrix} 5 & -6 \\ 1 & 0 \end{pmatrix}^{n+1} \begin{pmatrix} a_1 \\ a_0 \end{pmatrix} \label{e0.01} \end{align} である。ここにあらわれた行列 $\mat{A} = \begin{pmatrix}5 & -6 \\ 1& 0\end{pmatrix}$ の $n$ 乗の計算のために、$\mat{A}$ を対角化する。そのために必要な固有値方程式は、固有値を $\lambda$、固有ベクトルを $\begin{pmatrix}x \\ y\end{pmatrix}$ とすると \begin{align*} \mat{A} \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} 5 & -6 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = \lambda \begin{pmatrix} x \\ y \end{pmatrix} \end{align*} とあらわせる。このとき特性方程式は \begin{align*} \det(\mat{A} - \lambda\mat{E}) = \det \left\{ \begin{pmatrix} 5 & -6 \\ 1 & 0 \end{pmatrix} - \begin{pmatrix} \lambda & 0 \\ 0 & \lambda \end{pmatrix} \right\} = \det \begin{pmatrix} 5 - \lambda & -6 \\ 1 & -\lambda \end{pmatrix} = 0 \end{align*} となる。

この特性方程式をとくと \begin{align*} \det \begin{pmatrix} 5 - \lambda & -6 \\ 1 & -\lambda \end{pmatrix} = 0 \quad\therefore\; \lambda^2 - 5\lambda + 6 = 0 \quad\therefore\; (\lambda - 3)(\lambda -2) = 0 \end{align*} となって、異なる固有値が２個得られる（$\lambda_1 = 3$ と $\lambda_2 = 2$）。固有値が異なっているので、それぞれの固有値に対応する固有ベクトルは線型独立である。

まず $\lambda_1 = 3$ に対応する固有値方程式は \begin{align*} \begin{pmatrix} 5 & -6 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = 3 \begin{pmatrix} x \\ y \end{pmatrix} \quad\therefore\; \begin{pmatrix} 2 & -6 \\ 1 & -3 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix} \iff x - 3y = 0 \end{align*} であるから、これをみたす単純明快な固有ベクトルとして $\vec{v}_1 = \begin{pmatrix}3 \\ 1\end{pmatrix}$ を選ぶ。同様にして $\lambda_2 = 2$ に対応する固有値方程式は \begin{align*} \begin{pmatrix} 5 & -6 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = 2 \begin{pmatrix} x \\ y \end{pmatrix} \quad\therefore\; \begin{pmatrix} 3 & -6 \\ 1 & -2 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix} \iff x - 2y = 0 \end{align*} であるから、やはりこれをみたす単純な $\vec{v}_2 = \begin{pmatrix}2 \\ 1\end{pmatrix}$ を固有ベクトルとして選ぶ。

この２つの固有ベクトルを使って \begin{align*} \mat{P} = \begin{pmatrix}\vec{v}_1 & \vec{v}_2 \end{pmatrix} = \begin{pmatrix} 3 & 2 \\ 1 & 1 \end{pmatrix} \end{align*} を用意する。逆行列は簡単な計算により \begin{align*} \mat{P}^{-1} = \begin{pmatrix} 1 & -2 \\ -1 & 3 \end{pmatrix} \end{align*} ともとまる。$\mat{P}$ と $\mat{P}^{-1}$ を次のように $\mat{A}$ に作用させると \begin{align*} \mat{P}^{-1}\mat{A}\mat{P} = \begin{pmatrix} 1 & -2 \\ -1 & 3 \end{pmatrix} \begin{pmatrix} 5 & -6 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 3 & 2 \\ 1 & 1 \end{pmatrix} = \begin{pmatrix} 3 & 0 \\ 0 & 2 \end{pmatrix} =: \mat{D} \end{align*} という対角行列 $\mat{D}$ が得られる（上式の最後の「$=: \mat{D}$」は、計算結果の行列に $\mat{D}$ という名前をつけたということ）。この $\mat{D}$ はあきらかに固有値が対角成分になっている。この式にたいして左側から $\mat{P}$、右側から $\mat{P}^{-1}$ を施せば $\mat{A} = \mat{P}\mat{D}\mat{P}^{-1}$ となり、両辺をそれぞれ $n$ 乗して \begin{align*} \mat{A}^n = (\mat{P}\mat{D}\mat{P}^{-1})^n = \mat{P}\mat{D}\mat{P}^{-1}\mat{P}\mat{D}\mat{P}^{-1} \cdots \mat{P}\mat{D}\mat{P}^{-1} = \mat{P}\mat{D}^n\mat{P}^{-1} \end{align*} ともとまる。具体的な計算をすれば \begin{align*} \begin{pmatrix} 5 & -6 \\ 1 & 0 \end{pmatrix}^n &= \begin{pmatrix} 3 & 2 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} 3 & 0 \\ 0 & 2 \end{pmatrix}^n \begin{pmatrix} 1 & -2 \\ -1 & 3 \end{pmatrix} = \begin{pmatrix} 3 & 2 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} 3^n & 0 \\ 0 & 2^n \end{pmatrix} \begin{pmatrix} 1 & -2 \\ -1 & 3 \end{pmatrix} \\ &= \begin{pmatrix} 3^{n+1} - 2^{n+1} & -2 \cdot 3^{n+1} + 3 \cdot 2^{n+1} \\ 3^n - 2^n & -2 \cdot 3^n + 3 \cdot 2^n \end{pmatrix} \end{align*} であり、これを\eqref{e0.01}にあてはめれば \begin{align*} \begin{pmatrix} a_{n+2} \\ a_{n+1} \end{pmatrix} = \begin{pmatrix} 5 & -6 \\ 1 & 0 \end{pmatrix}^{n+1} \begin{pmatrix} a_1 \\ a_0 \end{pmatrix} = \begin{pmatrix} 3^{n+2} - 2^{n+2} & -2 \cdot 3^{n+2} + 3 \cdot 2^{n+2} \\ 3^{n+1} - 2^{n+1} & -2 \cdot 3^{n+1} + 3 \cdot 2^{n+2} \end{pmatrix} \begin{pmatrix} a_1 \\ a_0 \end{pmatrix} \end{align*} となる。サフィックスと冪乗の値にに留意して $a_{n}$ をとりだせば \begin{align*} a_n = (3^n - 2^n)a_1 + (-2 \cdot 3^n + 3 \cdot 2^n)a_0 \end{align*} となって、特性方程式やシフト演算子を使った場合と同じ結果を得ることが確認できる。

第４章 定数項のある３項間漸化式の場合

$a_{n+2} = p a_{n+1} + q a_{n} + r$ という、3項間漸化式に $r$ という定数項がついている多少一般的な場合を考えてみる。


$\blacksquare$ 特性方程式を使って

$\square$ 解法１

定数項がない場合の特性方程式を用いる解法を先に見た（「第１章 漸化式の特性方程式をを使って解く」参照）。なので、ここでもなんとか定数項のない形に持ち込めればいいのではないかというのが第一感である。実際 $a_{n} = a^{\prime}_{n} + s$ とすると \begin{align*} a_{n+2} = p a_{n+1} + q a_{n} + r \iff a^{\prime}_{n+2} + s = p (a^{\prime}_{n+1} + s) + q (a^{\prime}_{n} + s) + r \iff a^{\prime}_{n+2} = p a^{\prime}_{n+1} + q a^{\prime}_{n} + \{(p + q - 1)s + r\} \end{align*} となるから、$s = r/\{1-(p+q)\}$ という $s$ を選べば、定数項のない３項間漸化式 $a^{\prime}_{n+2} = p a^{\prime}_{n+1} + q a^{\prime}_{n}$ が得られるので、それを特性方程式を用いて解けば良い。

ただし、$p + q = 1$ のときには、$s$ を選ぶことはできない（$0$ による除算となるので、決められない）。しからば、$p + q = 1$ のときにはどうすればいいだろうか？そもそもの式に立ち返れば \begin{align*} a_{n+2} = p a_{n+1} + q a_{n} + r \iff a_{n+2} = (1 - q) a_{n+1} + q a_{n} + r \iff a_{n+2} - a_{n+1} = -q(a_{n+1} - a_{n}) + r \end{align*} となる。ここで、$d_{n} = a_{n+1} - a_{n}$ とおけば \begin{align*} d_{n+1} = -q d_{n} + r \end{align*} という形の、定数項のある２項間漸化式が得られる。それゆえこれを解けば良いことになる。２項間漸化式の解法については、「補遺２ ２項間漸化式をめぐって」でまとめておいた。そこでの結果を使うと \begin{align*} d_{n} = \begin{cases} \, (-q)^n d_0 + \dfrac{(-q)^n - 1}{(-q) - 1}r &\quad(-q \neq 1) \\ \, d_0 + nr &\quad(-q = 1) \end{cases} \end{align*} となる。あとは、ここから $a_{n}$ を求めれば良い。

「あとは、ここから $a_{n}$ を求めれば良い。」とは書いてみたものの、その先は少し複雑である。

$\square$ 解法２

もう一つの解法をみておく。ここでもまず $a_{n+2} - p a_{n+1} - q a_{n} = r$ といったん変形してから \begin{align*} a_{n+2} - p a_{n+1} - q a_{n} = a_{n+2} - (\alpha + \beta) a_{n+1} + (\alpha\beta) a_{n} \end{align*} というように同値変形ができたとする。この右辺をばらせば \begin{align*} a_{n+2} - p a_{n+1} - q a_{n} \iff \begin{cases} \, a_{n+2} - \beta a_{n+1} - \alpha(a_{n+1} - \beta a_{n}) \\ \, a_{n+2} - \alpha a_{n+1} - \beta(a_{n+1} - \alpha a_{n}) \end{cases} \end{align*} となるから、元の漸化式は最終的に \begin{align*} a_{n+2} - p a_{n+1} - q a_{n} = r \iff \begin{cases} \, a_{n+2} - \beta a_{n+1} = \alpha(a_{n+1} - \beta a_{n}) + r \\ \, a_{n+2} - \alpha a_{n+1} = \beta(a_{n+1} - \alpha a_{n}) + r \end{cases} \end{align*} となる。そしてここでも $b_{n} = a_{n+1} - \beta a_{n},\, c_{n} = a_{n+1} - \alpha a_{n}$ と置き換えると \begin{align} \begin{cases} \, b_{n+1} = \alpha b_{n} + r \\ \, c_{n+1} = \beta c_{n} + r \end{cases} \label{c1.01} \end{align} となって、定数項のある２項間漸化式が２つ現れてくる。

この道中でもわかるように、定数項のある場合でも、定数項のない場合と同一の特性方程式の解 $\alpha$ と $\beta$ を使って、定数項のある２項間漸化式をもとめ出し、それを解けばいいことになる。もちろん $\alpha = \beta$ という重根の場合には別の工夫が必要になることも、定数項のない場合と同様である（「補遺１ 重根の場合（縮退の場合）」の「$\blacksquare$ ３項間漸化式が定数項を持ち、かつ、その特性方程式が重根を持つ場合」で詳細を記した）。

\eqref{c1.01} を解けば良いのだが、「補遺２ ２項間漸化式をめぐって」を見ればわかるように、$\alpha$ が $1$ のときとそうでないときで、$b_{n}$ の形式は異なる。同様に、$\beta$ が $1$ のときとそうでないときでも $c_{n}$ の形は異なる。したがって、$\alpha$ と $\beta$ に対して４通りの組み合わせを考えることが必要になってくる。見通しは立っているのだが、実際に書こうとするとかなり煩雑になることが予想される。なので一般的な形をのべることは割愛させてもらう（教科書執筆者ならば、練習問題とするところだろう）。


$\blacksquare$ シフト演算子 $\hat{L}$ を使って

この漸化式を素直に $\hat{L}$ を使ってあらわすと \begin{align*} \hat{L}^2 a_{n} - p\hat{L}a_{n} - q a_{n} - r = 0 \end{align*} となる。したがって、定数項が邪魔になってこのままでは因数分解できない。ゆえに、上で述べた特性方程式での解法１を使って定数項のない３項間漸化式に変形し、それを解くのが王道である。実際、解法１の $s$ を使って $a_{n} = a^{\prime}_n + s$ とすると、$\hat{L}$ は数列の項以外には何の作用も及さなかったから \begin{align*} \hat{L}^2 a_{n} - p\hat{L}a_{n} - q a_{n} - r &= \hat{L}^2 (a^{\prime}_{n} + s) - p\hat{L}(a^{\prime}_{n} + s) - q(a^{\prime}_{n} + s) - r \\ &= \hat{L}^2 a^{\prime}_{n} - p\hat{L}a^{\prime}_{n} - q a^{\prime}_{n} + \{(1 - (p + q)\}s - r \\ &= \hat{L}^2 a^{\prime}_{n} - p\hat{L}a^{\prime}_{n} - q a^{\prime}_{n} = 0 \end{align*} という漸化式に帰着するのである。

上の特性方程式を使った解法１で見たように、$s$ が求められない場合は（つまり $p + q = 1$ の場合は）、そもそもの漸化式が２項間漸化式になるのでそれを解いてしまえばよい。わざわざ $\hat{L}$ を使うまでもなかろう。


$\blacksquare$ 行列の対角化を使って

行列の対角化を使って求める方法についても、上で述べた特性方程式での解法１を使って定数項のない３項間漸化式に変形し、それを解くのが王道であることは変わらない。しかしながら、対角行列の冪乗の性質をつかうと、定数項を残したままでも求めることができる。すこし寄り道になるが、その解法の仕組みを見ておこう。

定数項のある３項間漸化式を行列であらわすと \begin{align} \begin{pmatrix} a_{n+2} \\ a_{n+1} \end{pmatrix} = \begin{pmatrix} p & q \\ 1 & 0 \end{pmatrix} \begin{pmatrix} a_{n+1} \\ a_{n} \end{pmatrix} + \begin{pmatrix} r \\ 0 \end{pmatrix} \label{c3.01} \end{align} である。これからの計算の見通しを良くするために $ \mat{A} = \begin{pmatrix} p & q \\ 1 & 0 \end{pmatrix} ,\, \vec{a}_n = \begin{pmatrix} a_{n+1} \\ a_{n} \end{pmatrix} ,\, \vec{r} = \begin{pmatrix} r \\ 0 \end{pmatrix} $ とあらわすことにすると \begin{align*} \eqref{c3.01} \iff \vec{a}_{n+1} = \mat{A}\vec{a}_{n} + \vec{r} \end{align*} となる。ここで $n$ を順次繰り下げていけば \begin{align*} \vec{a}_{n+1} &= \mat{A}\vec{a}_{n} + \vec{r} \\ &= \mat{A}(\mat{A}\vec{a}_{n-1} + \vec{r}) + \vec{r} \\ &= \mat{A}^2\vec{a}_{n-1} + \mat{A}\vec{r} + \vec{r} \\ &= \mat{A}^3\vec{a}_{n-2} + \mat{A}^2\vec{r} + \mat{A}\vec{r} + \vec{r} \\ &= \cdots \\ &= \mat{A}^{n+1}\vec{a}_0 + \left\{\mat{A}^n + \mat{A}^{n-1} + \cdots + \mat{A} + \mat{E}\right\}\vec{r} \end{align*} となる（$\mat{E}$ は単位行列）。

さてここで、固有値方程式の助けを借りることによって $\mat{P}^{-1}\mat{A}\mat{P} = \mat{D}$ というように固有値からなる対角行列 $\mat{D}$ が求まったとしよう（為念。ここからは $\mat{A}$ が対角化できた場合に限っての話である）。するとそこから $\mat{A}^n$ が計算できて \begin{align*} \mat{A}^n = \mat{P}\mat{D}^n\mat{P}^{-1} \end{align*} となることは、「第３章 行列の対角化を使って解く」のところで見てきた。残るは \begin{align*} \mat{A}^n + \mat{A}^{n-1} + \cdots + \mat{A} + \mat{E} = \sum_{k=0}^n \mat{A}^k \end{align*} の計算である。ふたたび $\mat{D} = \mat{P}^{-1}\mat{A}\mat{P}$ を利用すると \begin{align*} \sum_{k=0}^n \mat{D}^k = \sum_{k=0}^n (\mat{P}^{-1}\mat{A}\mat{P})^k = \sum_{k=0}^n \mat{P}^{-1}\mat{A}^k\mat{P} = \mat{P}^{-1}\left(\sum_{k=0}^n \mat{A}^k\right)\mat{P} \end{align*} となるから \begin{align*} \sum_{k=0}^n \mat{A}^k = \mat{P}\left(\sum_{k=0}^n \mat{D}^k\right)\mat{P}^{-1} \end{align*} という計算で求まることになる[4-1]。そして $\mat{D}$ は対角行列なのであるから、冪乗の計算はたやすい。

以上から、一般項が \begin{align*} \vec{a}_{n+1} = \mat{A}^{n+1}\vec{a}_0 + \left\{\mat{A}^n + \mat{A}^{n-1} + \cdots + \mat{A} + \mat{E}\right\}\vec{r} = \mat{P}\mat{D}^{n+1}\mat{P}^{-1}\vec{a}_0 + \left\{\mat{P}\left(\sum_{k=0}^n \mat{D}^k\right)\mat{P}^{-1}\right\}\vec{r} \end{align*} というように、対角行列の冪乗の計算に還元されて求まる。


第４章の脚註

[4-1]  一般化を試みる。行列 $\mat{X}$ の冪乗であらわされる、係数が $1$ の多項式 $F_1(\mat{X})$ は \begin{align*} F_1(\mat{X}) = \mat{X}^1 + \mat{X}^2 + \cdots + \mat{X}^n = \sum_{k=1}^n \mat{X}^k \end{align*} と書ける。ここで $\mat{X} = \mat{P}^{-1}\mat{A}\mat{P}$ あらわせたとすると、 \begin{align*} F_1(\mat{P}^{-1}\mat{A}\mat{P}) = \sum_{k=1}^n \left(\mat{P}^{-1}\mat{A}\mat{P}\right)^k = \sum_{k=1}^n \mat{P}^{-1}\mat{A}^k\mat{P} = \mat{P}^{-1}\left(\sum_{k=1}^n \mat{A}^k\right)\mat{P} = \mat{P}^{-1}F_1(\mat{A})\mat{P} \end{align*} という形式が導き出せる。$\mat{X} = \mat{P}\mat{A}\mat{P}^{-1}$ とあらわせる場合も同様で、 \begin{align*} F_1(\mat{P}\mat{A}\mat{P}^{-1}) = \sum_{k=1}^n \left(\mat{P}\mat{A}\mat{P}^{-1}\right)^k = \sum_{k=1}^n \mat{P}\mat{A}^k\mat{P}^{-1} = \mat{P}\left(\sum_{k=1}^n \mat{A}^k\right)\mat{P}^{-1} = \mat{P}F_1(\mat{A})\mat{P}^{-1} \end{align*} となる。本文の場合は、この $\mat{X}$ が、$\mat{A}$ を対角化した行列の $\mat{D}$ の例であるが、この形式はべつに対角行列でなくても成立するものなのである。

多項式の係数にバリエーションを加える。つまり、「すべての係数が $1$ である」という特殊な条件ではなく、「定数であればなんでもよい」という膨らみを持たせるのである。その多項式 $F_p(\mat{X})$ を、定数係数を $\eta_k\;(k=1,2,\ldots,n)$ として \begin{align*} F_p(\mat{X}) = \eta_1\mat{X}^1 + \eta_2\mat{X}^2 + \cdots + \eta_n\mat{X}^n = \sum_{k=1}^n \eta_k\mat{X}^k \end{align*} とあらわすことにする。上の場合と同様に $\mat{X} = \mat{P}^{-1}\mat{A}\mat{P}$ であるときには \begin{align*} F_p(\mat{P}^{-1}\mat{A}\mat{P}) = \sum_{k=1}^n \eta_k\left(\mat{P}^{-1}\mat{A}\mat{P}\right)^k = \sum_{k=1}^n \eta_k\mat{P}^{-1}\mat{A}^k\mat{P} = \mat{P}^{-1}\left(\sum_{k=1}^n \eta_k\mat{A}^k\right)\mat{P} = \mat{P}^{-1}F_p(\mat{A})\mat{P} \end{align*} という形式が導き出せる。$\mat{X} = \mat{P}\mat{A}\mat{P}^{-1}$ のときも同様で、 \begin{align*} F_p(\mat{P}\mat{A}\mat{P}^{-1}) = \sum_{k=1}^n \eta_k\left(\mat{P}\mat{A}\mat{P}^{-1}\right)^k = \sum_{k=1}^n \eta_k\mat{P}\mat{A}^k\mat{P}^{-1} = \mat{P}\left(\sum_{k=1}^n \eta_k\mat{A}^k\right)\mat{P}^{-1} = \mat{P}F_p(\mat{A})\mat{P}^{-1} \end{align*} となる。

さてつぎに関数について思いを馳せる。関数は、定数係数の多項式で近似できるから（関数のテーラー展開を想像しよう）、上記の形式は関数についても成立するだろうと予想できる。つまり \begin{align*} & F(\mat{P}^{-1}\mat{A}\mat{P}) = \mat{P}^{-1}F(\mat{A})\mat{P} \\ & F(\mat{P}\mat{A}\mat{P}^{-1}) = \mat{P}F(\mat{A})\mat{P}^{-1} \end{align*} が成立するだろうということだ。厳密に等しいというには、$\sum$ を無限項まで取る必要があるだろうが、有限項まででも近似にはなっているはずである。

エクササイズ２： $a_{n+2} = 5 a_{n+1} - 6 a_{n} + 4$ の一般項を求める

$\blacksquare$ 特性方程式を使って

【解法１】

定数項のない３項間漸化式に変形する解法である（本文の所で述べた解法１）。$a_{n} = a^{\prime}_n + s$ とずらした数列 $a^{\prime}_n$ を考えると、問題の式は次のように同値変形できる： \begin{align*} a_{n+2} = 5 a_{n+1} - 6 a_{n} + 4 \iff a^{\prime}_{n+2} + s = 5(a^{\prime}_{n+1} + s) - 6(a^{\prime}_{n} + s) + 4 \iff a^{\prime}_{n+2} - 5a^{\prime}_{n+1} + 6a^{\prime}_{n} = 4 - 2s \;. \end{align*} したがって、$s = 2$ とすることにより \begin{align*} a^{\prime}_{n+2} - 5a^{\prime}_{n+1} + 6a^{\prime}_{n} = 0 \end{align*} という、エクササイズ１と同じ形式の３項間漸化式がえられる。したがって、その解を使えば \begin{align*} & a^{\prime}_{n} = 3^n(a^{\prime}_1 - 2a^{\prime}_0) - 2^n(a^{\prime}_1 - 3a^{\prime}_0) \\ & \therefore\; a_{n} - 2 = 3^n((a_1 -2) - 2(a_0 - 2)) - 2^n((a_1 - 2) - 3(a_0 - 2)) \\ & \therefore\; a_{n} = 3^n(a_1 - 2a_0 + 2) - 2^n(a_1 - 3a_0 +4) + 2 \end{align*} ともとまる。仮に $a_0 = a_1 =1$ とすれば $a_{n} = 3^n - 2^{n+1} + 2$ である。

【解法２】

定数項をそのままにして解く方法である（本文の所で述べた解法２）。２項間漸化式の解法の練習もかねて実践する。

特性方程式は $x^2 - 5x + 6 = (x-2)(x-3) = 0$ となるから、そもそもの漸化式 $a_{n+2} = 5a_{n+1} - 6a_{n} + 4$ は次の２式と同値になる： \begin{align} & (a_{n+2} - 2a_{n+1}) - 3(a_{n+1} - 2a_{n}) = 4 \;, \label{e1.01} \\ & (a_{n+2} - 3a_{n+1}) - 2(a_{n+1} - 3a_{n}) = 4 \;. \label{e1.02} \end{align} ここで $b_{n} = a_{n+1} - 2a_{n},\, c_{n} = a_{n+1} - 3a_{n}$ と置くことにする。すると \begin{align*} \eqref{e1.01} \iff b_{n+1} - 3b_{n} = 4 \end{align*} という定数項を含む２項間漸化式が得られる。この特性方程式は $x - 3x = 4$ だから、$x = -2$ という解が得られ、これを使えば \begin{align*} b_{n+1} - 3b_{n} = 4 \iff b_{n+1} + 2 = 3(b_{n} + 2) \end{align*} という等比数列に変形できる。したがって、$(b_{n} + 2) = (b_0 + 2)3^n$、すなわち $b_{n} = (b_0 + 2)3^n - 2$。

同様に \begin{align*} \eqref{e1.02} \iff c_{n+1} - 2c_{n} = 4 \end{align*} という定数項を含む２項間漸化式も得られる。この特性方程式は $x - 2x = 4$ だから、解は $x = -4$ であり、これを使えば \begin{align*} c_{n+1} - 2c_{n} = 4 \iff c_{n+1} + 4 = 2(c_{n} + 4) \end{align*} という等比数列が導出できて、$(c_{n} + 4) = (c_0 + 4)2^n$。ゆえに $c_{n} = (c_0 + 4)2^n - 4$。

$b_{n},\, c_{n}$ をもとの形に戻せば \begin{align*} & b_{n} = (b_0 + 2)3^n - 2 \iff a_{n+1} - 2a_{n} = (b_0 + 2)3^n - 2 \\ & c_{n} = (c_0 + 4)2^n - 4 \iff a_{n+1} - 3a_{n} = (c_0 + 4)2^n - 4 \end{align*} であるから、$a_{n+1}$ を消去して \begin{align*} a_{n} = (b_0 + 2)3^n - (c_0 + 4)2^n + 2 \end{align*} が得られる。そして $b_{n},\,c_{n}$ の定義を振り返ると \begin{align*} & b_0 = a_1 - 2a_0 \;, \\ & c_0 = a_1 - 3a_0 \end{align*} だから、最終的な結果として \begin{align*} a_{n} = 3^n(a_1 - 2a_0 + 2) - 2^n(a_1 - 3a_0 + 4) + 2 \end{align*} が求まる。


$\blacksquare$ シフト演算子 $\hat{L}$ を使って

定数項が存在するままでシフト演算子 $\hat{L}$ を使うと \begin{align*} (\hat{L}^2 - 5\hat{L} + 6)a_{n} = (\hat{L} - 3)(\hat{L} - 2)a_{n} = 4 \end{align*} となって、ここからさきに進む道が見えない。したがって、定数項をなくした形にするのがよい、その先はエクササイズ１と一緒である。


$\blacksquare$ 行列の対角化を使って

こちらも定数項をなくした形に変形してエクササイズ１と同様な計算をすれば良いのだが、ここでは第４章 定数項のある３項間漸化式の場合のところで見た、定数項を残したままでのやりかたでやってみる。復習から始めよう。この漸化式を行列であらわすと \begin{align} \begin{pmatrix} a_{n+2} \\ a_{n+1} \end{pmatrix} = \begin{pmatrix} 5 & -6 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} a_{n+1} \\ a_{n} \end{pmatrix} + \begin{pmatrix} 4 \\ 0 \end{pmatrix} \label{e1.03} \end{align} である。ここで $ \mat{A} = \begin{pmatrix} 5 & -6 \\ 1 & 0 \end{pmatrix} ,\, \vec{a}_n = \begin{pmatrix} a_{n+1} \\ a_{n} \end{pmatrix} ,\, \vec{r} = \begin{pmatrix} 4 \\ 0 \end{pmatrix} $ とあらわすことにすると \begin{align*} \eqref{e1.03} \iff \vec{a}_{n+1} = \mat{A}\vec{a}_{n} + \vec{r} \end{align*} となる。$n$ を順次繰り下げていくことにより \begin{align} \vec{a}_{n+1} = \mat{A}^{n+1}\vec{a}_0 + \left\{\mat{A}^n + \mat{A}^{n-1} + \cdots + \mat{A} + \mat{E}\right\}\vec{r} = \mat{A}^{n+1}\vec{a}_0 + \left(\sum_{k=0}^n \mat{A}^k\right)\vec{r} \label{e1.04} \end{align} と一般項が求まるのであった（$\mat{E}$ は単位行列）。そして、固有値が縮退していない場合には、固有値方程式の助けを借りることによって $\mat{P}^{-1}\mat{A}\mat{P} = \mat{D}$ というように固有値からなる対角行列 $\mat{D}$ が求まり、その結果 \begin{align*} \mat{A}^n = \mat{P}\mat{D}^n\mat{P}^{-1} \end{align*} が得られたのであった。また \begin{align*} \sum_{k=0}^n \mat{A}^k = \mat{P}\left(\sum_{k=0}^n \mat{D}^k\right)\mat{P}^{-1} \end{align*} という結果も得ていた。

この問の具体例にもどる。$\mat{A}$ の $n$乗はエクササイズ１ですでに解いてあって、 \begin{align*} \mat{A}^n = \begin{pmatrix} 5 & -6 \\ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} 3^{n+1} - 2^{n+1} & -2 \cdot 3^{n+1} + 3 \cdot 2^{n+1} \\ 3^n - 2^n & -2 \cdot 3^n + 3 \cdot 2^n \end{pmatrix} \end{align*} である。同様にエクササイズ１で対角行列 $\mat{D} = \begin{pmatrix}3 & 0 \\ 0 & 2\end{pmatrix}$ と求めてあったので、 \begin{align*} \sum_{k=0}^n \mat{D}^k = \sum_{k=0}^n \begin{pmatrix} 3 & 0 \\ 0 & 2 \end{pmatrix}^k = \sum_{k=0}^n \begin{pmatrix} 3^k & 0 \\ 0 & 2^k \end{pmatrix} = \begin{pmatrix} \sum_{k=0}^n 3^k & 0 \\ 0 & \sum_{k=0}^n 2^k \end{pmatrix} = \begin{pmatrix} (3^{n+1} - 1)/2 & 0 \\ 0 & 2^{n+1} - 1 \end{pmatrix} \end{align*} となる（公比数列の $n$ 項までの和を計算した）。すでに求めてあった $\mat{P} = \begin{pmatrix} 3 & 2 \\ 1 & 1\end{pmatrix},\, \mat{P}^{-1} = \begin{pmatrix} 1 & -2 \\ -1 & 3\end{pmatrix}$ を使えば \begin{align*} \sum_{k=0}^n \mat{A}^k = \mat{P}\left(\sum_{k=0}^n \mat{D}^k\right)\mat{P}^{-1} &= \begin{pmatrix} 3 & 2 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} (3^{n+1} - 1)/2 & 0 \\ 0 & 2^{n+1} - 1 \end{pmatrix} \begin{pmatrix} 1 & -2 \\ -1 & 3 \end{pmatrix} \\ &= \begin{pmatrix} 3 & 2 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} (3^{n+1} - 1)/2 & 1 - 3^{n+1} \\ 1 - 2^{n+1} & 3\cdot(2^{n+1} - 1) \end{pmatrix} \\ &= \begin{pmatrix} \dfrac{3}{2}(3^{n+1} -1) + 2(1 - 2^{n+1}) & 3(1 - 3^{n+1}) + 6\cdot(2^{n+1} - 1) \\ \dfrac{1}{2}(3^{n+1} -1) + (1 - 2^{n+1}) & (1 - 3^{n+1}) + 3\cdot(2^{n+1} - 1) \end{pmatrix} \;. \end{align*} ゆえに \begin{align*} \left(\sum_{k=0}^n \mat{A}^k\right)\vec{r} &= \begin{pmatrix} \dfrac{3}{2}\cdot(3^{n+1} - 1) - 2\cdot(2^{n+1} - 1) & -3\cdot(3^{n+1} - 1) + 2\cdot 3\cdot(2^{n+1} - 1) \\ \dfrac{1}{2}\cdot(3^{n+1} - 1) - (2^{n+1} - 1) & -(3^{n+1} - 1) + 3\cdot(2^{n+1} - 1) \\ \end{pmatrix} \begin{pmatrix} 4 \\ 0 \end{pmatrix} \\ &= \begin{pmatrix} 6\cdot(3^{n+1} -1) - 8\cdot(2^{n+1} - 1) \\ 2\cdot(3^{n+1} -1) - 4\cdot(2^{n+1} - 1) \end{pmatrix} \\ &= \begin{pmatrix} 2\cdot 3^{n+2} - 2^{n+4} + 2 \\ 2\cdot 3^{n+1} - 2^{n+3} + 2 \end{pmatrix} \;. \end{align*} 以上の結果をすべて\eqref{e1.04}に適用すると \begin{align*} & \vec{a}_{n+1} = \mat{A}^{n+1}\vec{a}_0 + \left(\sum_{k=0}^n \mat{A}^k\right)\vec{r} \\ & \qquad\iff \\ & \begin{pmatrix} a_{n+2} \\ a_{n+1} \end{pmatrix} = \begin{pmatrix} 3^{n+2} - 2^{n+2} & -2 \cdot 3^{n+2} + 3 \cdot 2^{n+2} \\ 3^{n+1} - 2^{n+1} & -2 \cdot 3^{n+1} + 3 \cdot 2^{n+1} \end{pmatrix} \begin{pmatrix} a_1 \\ a_0 \end{pmatrix} + \begin{pmatrix} 2\cdot 3^{n+2} - 2^{n+4} + 2 \\ 2\cdot 3^{n+1} - 2^{n+3} + 2 \end{pmatrix} \end{align*} となって \begin{align*} a_{n+1} &= (3^{n+1} - 2^{n+1})a_1 + (-2 \cdot 3^{n+1} + 3 \cdot 2^{n+1})a_0 + (2\cdot 3^{n+1} - 2^{n+3} + 2) \\ &= 3^{n+1}(a_1 - 2a_0 + 2) - 2^{n+1}(a_1 - 3a_0 + 4) + 2 \\ \end{align*} と求めることができる。第$n$項にすれば \begin{align*} a_n = 3^n(a_1 - 2a_0 + 2) - 2^n(a_1 - 3a_0 + 4) + 2 \;. \end{align*}

第５章 フィボナッチ数列の一般項を求める

ここまでくれば、フィボナッチ数列 $a_{n+2} = a_{n+1} + a_{n}$ の一般項をもとめることは、造作もない。

$\blacksquare$ 特性方程式を使って

フィボナッチ数列の特性方程式の解を $\alpha,\, \beta$ とすると \begin{align*} x^2 - x - 1 = 0 \quad\therefore\; \alpha = \frac{1 + \sqrt{5}}{2},\; \beta = \frac{1 - \sqrt{5}}{2} \end{align*} となる（もちろん $\alpha$ と $\beta$ が逆でも良い）。これより \begin{align*} & a_{n+1} - \alpha a_{n} = \beta^n(a_1 - \alpha a_0) \\ & a_{n+1} - \beta a_{n} = \alpha^n(a_1 - \beta a_0) \end{align*} が導出できる。そして、フィボナッチ数列では、$a_0 = 0,\, a_1 = 1$ であるから（フィボナッチ数列の定義でもある） \begin{align*} & a_{n+1} - \alpha a_{n} = \beta^n \\ & a_{n+1} - \beta a_{n} = \alpha^n \end{align*} となり、それゆえ \begin{align*} (\beta - \alpha) a_{n} = \beta^n - \alpha^n \quad\therefore\; a_{n} = \frac{\beta^n - \alpha^n}{\beta - \alpha} = \frac{1}{\sqrt{5}}\left\{\left(\dfrac{1+\sqrt{5}}{2}\right)^n - \left(\dfrac{1-\sqrt{5}}{2}\right)^n\right\} \;. \end{align*} （ちなみに、$1 - \alpha = \beta,\, 1 - \beta = \alpha$ という関係もある。$a_1 = 1,\,a_2 = 1$ から始める場合にはこれを使うと便利である。）


$\blacksquare$ シフト演算子 $\hat{L}$ を使って

シフト演算子 $\hat{L}$ を使うと、フィボナッチ数列の漸化式は \begin{align*} \hat{L}^2a_{n} - \hat{L}a_{n} - a_{n} = (\hat{L}^2 - \hat{L} - 1)a_{n} = (\hat{L} - \alpha)(\hat{L} - \beta)a_{n} = 0 \end{align*} とあらわせる。したがって、一般項 $a_{n}$ は、公比 $\alpha$ の等比数列と、公比 $\beta$ の等比数列の線型結合となるから \begin{align*} a_{n} = \mu \alpha^n + \nu \beta^n \end{align*} とあらわせる。フィボナッチ数列の初期条件は、$a_0 = 0,\, a_1 = 1$。したがって \begin{align*} \begin{cases} \, a_0 = \mu + \nu = 0 \\ \, a_1 = \mu\alpha + \nu\beta = 1 \end{cases} \quad\therefore\; \begin{cases} \, \mu = 1/(\alpha - \beta) \\ \, \nu = 1/(\beta - \alpha) \end{cases} \end{align*} さて $\hat{L}^2 - \hat{L} - 1 = (\hat{L} - \alpha)(\hat{L} - \beta)$ となる $\alpha$ と $\beta$ は、$\hat{L}^2 - \hat{L} - 1 = 0$ という方程式をとくことにより、 \begin{align*} \alpha = \frac{1 + \sqrt{5}}{2} \;,\quad \beta = \frac{1 - \sqrt{5}}{2} \end{align*} である（くどいけれども、もちろん $\alpha$ と $\beta$ が逆でもいい。結果はかわらない）。そしてこのとき \begin{align*} \alpha - \beta = \sqrt{5} \;,\quad \beta - \alpha = -\sqrt{5} \end{align*} となるから \begin{align*} \mu = \frac{1}{\sqrt{5}} \;,\quad \nu = - \frac{1}{\sqrt{5}} \end{align*} と求まって、一般項は \begin{align*} a_{n} = \frac{1}{\sqrt{5}}\left\{\left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n\right\} \;. \end{align*}


$\blacksquare$ 行列の対角化を使って

行列であらわすと \begin{align} \begin{pmatrix} a_{n+2} \\ a_{n+1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} a_{n+1} \\ a_{n} \end{pmatrix} = \cdots = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n+1} \begin{pmatrix} a_1 \\ a_0 \end{pmatrix} \label{fib.01} \end{align} である。ここにあらわれた行列 $\mat{A} = \begin{pmatrix}1 & 1 \\ 1& 0\end{pmatrix}$ を対角化する。固有値方程式は、固有値を $\lambda$、固有ベクトルを $\begin{pmatrix}x \\ y\end{pmatrix}$ とすると \begin{align*} \mat{A} \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = \lambda \begin{pmatrix} x \\ y \end{pmatrix} \end{align*} となり、その特性方程式は \begin{align*} \det(\mat{A} - \lambda\mat{E}) = \det \left\{ \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} - \begin{pmatrix} \lambda & 0 \\ 0 & \lambda \end{pmatrix} \right\} = \det \begin{pmatrix} 1 - \lambda & 1 \\ 1 & -\lambda \end{pmatrix} = 0 \end{align*} となる。この特性方程式をとくと \begin{align*} \det \begin{pmatrix} 1 - \lambda & 1 \\ 1 & -\lambda \end{pmatrix} = 0 \quad\therefore\; \lambda^2 - \lambda - 1 = 0 \quad\therefore\; \lambda = \frac{1 + \sqrt{5}}{2},\, \frac{1 - \sqrt{5}}{2} \end{align*} と２つの異なる固有値が得られる（おのおのを $\lambda_1 = (1 + \sqrt{5})/2,\, \lambda_2 = (1 - \sqrt{5})/2$ と名付けておく）。固有値が異なっているので、それぞれの固有値に対応する固有ベクトルは互いに線型独立である。

まず $\lambda_1$ に対応する固有値方程式は \begin{align} \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = \lambda_1 \begin{pmatrix} x \\ y \end{pmatrix} \quad\therefore\; \begin{pmatrix} 1 - \lambda_1 & 1 \\ 1 & -\lambda_1 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix} \iff \begin{cases} \, (1 - \lambda_1)x + y = 0 \\ \, x - \lambda_1 y = 0 \end{cases} \label{fib.02} \end{align} である。したがって固有ベクトルとして $\begin{pmatrix}1 \\ \lambda_1-1\end{pmatrix},\, \begin{pmatrix}1/(\lambda_1-1) \\ 1\end{pmatrix},\, \begin{pmatrix} \lambda_1 \\ 1\end{pmatrix}$ などが存在する（このベクトルどれもが\eqref{fib.02}の結果を満たしていることは、$x,\, y$ にそれぞれを代入して辛抱強く計算することによって確認できる。その際には、$\lambda_1^2 - \lambda_1 - 1 = 0$ というこの場合の固有値の性質（特性方程式の解であること）を利用する）。それゆえ、最もわかりやすい $\vec{v}_1 = \begin{pmatrix}\lambda_1 \\ 1\end{pmatrix}$ を固有ベクトルして選んでおく。

もう一つの固有値 $\lambda_2 = 2$ についてもまったく同じ理路が成り立ち、その結果から、$\vec{v}_2 = \begin{pmatrix}\lambda_2 \\ 1\end{pmatrix}$ を固有ベクトルとして選ぶことにする。

この２つの固有ベクトルを使って \begin{align*} \mat{P} = \begin{pmatrix}\vec{v}_1 & \vec{v}_2 \end{pmatrix} = \begin{pmatrix} \lambda_1 & \lambda_2 \\ 1 & 1 \end{pmatrix} \end{align*} を用意する。逆行列は簡単な計算により \begin{align*} \mat{P}^{-1} = \frac{1}{\lambda_1 - \lambda_2} \begin{pmatrix} 1 & -\lambda_2 \\ -1 & \lambda_1 \end{pmatrix} \end{align*} ともとまる。この$\mat{P},\, \mat{P}^{-1}$ によって \begin{align*} \mat{P}^{-1}\mat{A}\mat{P} = \begin{pmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{pmatrix} \end{align*} という対角行列が得られるのだから \begin{align*} \mat{A}^n = \mat{P}\begin{pmatrix}\lambda_1 & 0 \\ 0 & \lambda_2\end{pmatrix}^n\mat{P}^{-1} = \mat{P}\begin{pmatrix}(\lambda_1)^n & 0 \\ 0 & (\lambda_2)^n\end{pmatrix}\mat{P}^{-1} \end{align*} となる。具体的な計算を実行すると \begin{align*} \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n = \frac{1}{\lambda_1 - \lambda_2} \begin{pmatrix} \lambda_1 & \lambda_2 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} (\lambda_1)^n & 0 \\ 0 & (\lambda_2)^n \end{pmatrix} \begin{pmatrix} 1 & -\lambda_2 \\ -1 & \lambda_1 \end{pmatrix} = \frac{1}{\lambda_1 - \lambda_2} \begin{pmatrix} (\lambda_1)^{n+1} - (\lambda_2)^{n+1} & \lambda_1\lambda_2\{(\lambda_2)^n - (\lambda_1)^n\} \\ (\lambda_1)^n - (\lambda_2)^n & \lambda_1\lambda_2\{(\lambda_2)^{n-1} - (\lambda_1)^{n-1}\} \\ \end{pmatrix} \end{align*} だから、\eqref{fib.01}をひとつずらしたもの（数列のサフイックス $n$ に留意！）に適用して \begin{align*} \begin{pmatrix} a_{n+1} \\ a_{n} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n} \begin{pmatrix} a_1 \\ a_0 \end{pmatrix} = \frac{1}{\lambda_1 - \lambda_2} \begin{pmatrix} (\lambda_1)^{n+1} - (\lambda_2)^{n+1} & \lambda_1\lambda_2\{(\lambda_2)^n - (\lambda_1)^n\} \\ (\lambda_1)^n - (\lambda_2)^n & \lambda_1\lambda_2\{(\lambda_2)^{n-1} - (\lambda_1)^{n-1}) \\ \end{pmatrix} \begin{pmatrix} a_1 \\ a_0 \end{pmatrix} \end{align*} を得る。フィボナッチ数列の初期条件を $a_0 = 0, a_1 = 1$ を利用すれば \begin{align*} & \begin{pmatrix} a_{n+1} \\ a_{n} \end{pmatrix} = \frac{1}{\lambda_1 - \lambda_2} \begin{pmatrix} (\lambda_1)^{n+1} - (\lambda_2)^{n+1} & \lambda_1\lambda_2\{(\lambda_2)^n - (\lambda_1)^n) \\ (\lambda_1)^n - (\lambda_2)^n & \lambda_1\lambda_2\{(\lambda_2)^{n-1} - (\lambda_1)^{n-1}) \\ \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \frac{1}{\lambda_1 - \lambda_2} \begin{pmatrix} (\lambda_1)^{n+1} - (\lambda_2)^{n+1} \\ (\lambda_1)^n - (\lambda_2)^n \end{pmatrix} \\ & \therefore\; a_n = \frac{1}{\lambda_1 - \lambda_2}\{(\lambda_1)^n - (\lambda_2)^n\} = \frac{1}{\sqrt{5}}\left\{\left(\dfrac{1+\sqrt{5}}{2}\right)^n - \left(\dfrac{1-\sqrt{5}}{2}\right)^n\right\} \end{align*} である。

補遺１ 重根の場合（縮退の場合）

$\blacksquare$ ３項間漸化式の特性方程式が重根を持つ場合

$a_{n+2} = p a_{n+1} + q a_{n}$ という３項間漸化式の一般項をもとめる方法は、本文で今まで見てきたように、(1) 特性方程式を使う、(2) シフト演算子 $\hat{L}$ を使う、(3) 行列と固有値方程式を使う、という３通りの方法があた。そしてそれぞれに（若干混乱はするけれど）「特性方程式」と呼ぶ方程式があって、それぞれ \begin{align*} &(1):\quad x^2 - px - q = 0 \\ &(2):\quad \hat{L}^2 - p\hat{L} - q = 0 \\ &(3):\quad \lambda^2 - p\lambda - q = 0 \end{align*} というようにあらわしてきた。

さらにまた、今までは、この２次の特性方程式が異なる解 $\alpha$ と $\beta$ を持つ場合を中心に考察をしてきた。そして、「重根の場合は後でまとめて説明する」というようにして話を進めてきた。なので、ここで上記３通りの方法それぞれについて、重根を持つ場合を検討してみようと思う。

重根を持つ場合のみを想定するのだから、３項間漸化式は、その重根を $\alpha$ とあらわすことにすると \begin{align*} a_{n+2} = 2\alpha a_{n+1} - \alpha^2 a_{n} \iff a_{n+2} - 2\alpha a_{n+1} + \alpha^2 a_{n} = 0 \end{align*} という形になる。以下この漸化式をみたす数列の一般項を、上に書いた３種類の方法それぞれで求めることを試みていく。


(1) 特性方程式を使う方法

$a_{n+2} - 2\alpha a_{n+1} + \alpha^2 a_{n} = 0$ という３項間漸化式の特性方程式を解くと \begin{align*} x^2 - 2\alpha x + \alpha^2 = (x - \alpha)^2 = 0 \end{align*} となる。したがって \begin{align} a_{n+2} - \alpha a_{n+1} = \alpha(a_{n+1} - \alpha a_{n}) = \alpha^{n+1}(a_1 - \alpha a_0) \label{apdx1.01} \end{align} というような等比数列がひとつ求まるのだが、ひとつしか求まらないことも事実である。第１章 漸化式の特性方程式をを使って解くのところで見たように、重根ではなく2つの異なる解が存在する時は、２つの等比数列が求まってそこから $a_{n} = \cdots$ と一般項を導出できたのであったが、ひとつしかないので同じ方法は取れない。これが重根を持つときの特徴である。このままでは一般項は求まらないので、なにがしかの別の工夫が必要になる。さてどうするか。

$\square$ 「真っ直ぐ（と思われる）」解法

数列のサフィックスをうまく操作してみよう。\eqref{apdx1.01}から \begin{align*} a_{n} - \alpha a_{n-1} = \alpha^{n-1}(a_1 - \alpha a_0) \end{align*} であることをまず押さえておく。そして \begin{align*} a_{n-1} - \alpha a_{n-2} = \alpha^{n-2}(a_1 - \alpha a_0) \quad \therefore\; \alpha a_{n-1} - \alpha^2 a_{n-2} = \alpha^{n-1}(a_1 - \alpha a_0) \end{align*} であるから、これを順次適用していくと \begin{align*} a_{n} - \alpha a_{n-1} &= \alpha^{n-1}(a_1 - \alpha a_0) \\ \alpha a_{n-1} - \alpha^2 a_{n-2} &= \alpha^{n-1}(a_1 - \alpha a_0) \\ \cdots &= \cdots \\ \alpha^{n-2}a_2 - \alpha^{n-1} a_1 &= \alpha^{n-1}(a_1 - \alpha a_0) \\ \alpha^{n-1}a_1 - \alpha^{n}a_0 &= \alpha^{n-1}(a_1 - \alpha a_0) \end{align*} と並べることができる。そして両辺の和をとって整理すると \begin{align*} & a_{n} - \alpha^{n} a_0 = \sum_{k=0}^{n-1}\alpha^{n-1}(a_1 - \alpha a_0) = \alpha^{n-1}(a_1 - \alpha a_0)\sum_{k=0}^{n-1}1 \\ & \therefore\; a_{n} - \alpha^{n} a_0 = n\alpha^{n-1}(a_1 - \alpha a_0) \quad \therefore\; a_{n} = n\alpha^{n-1} a_1 + (1 - n)\alpha^{n} a_0 \end{align*} と一般項が求まるのである。

$\square$ 別解

こういうやり方もある。 \begin{align*} a_{n+1} - \alpha a_{n} = \alpha^{n}(a_1 - \alpha a_0) \end{align*} において $a_1 - \alpha a_0$ は $n$ に依存しない定数であるので、これを $A$ とすると \begin{align*} a_{n+1} - \alpha a_{n} = \alpha^n A \;. \end{align*} つぎに両辺を $\alpha^{n+1}$ で割って整理しようと思うが，よくみると $\alpha = 0$ のときにはこの割り算は実施できない。けれども、$\alpha = 0$ ならばそもそもの３項間漸化式が $a_{n+2} = 0$ となるので、すべての項が $0$ であることになる。つまり $\alpha = 0$ のときの一般項は $a_{n} = 0$。したがって、以下では $\alpha \neq 0$ であるとする。すると \begin{align*} \frac{a_{n+1}}{\alpha^{n+1}} - \frac{a_{n}}{\alpha^n} = \frac{A}{\alpha} \;. \end{align*} $b_{n} = a_{n}/\alpha^n$ と書き換えると \begin{align*} b_{n+1} - b_{n} = \frac{A}{\alpha} \end{align*} となって、数列 $(b_{n})$ は等差 $A/\alpha$ の等差数列。したがって一般項は \begin{align*} b_{n} = b_0 + \frac{A}{\alpha} n \;. \end{align*} この結果を $a_{n}$ であらわすと、$b_0 = a_0$ であり $A = a_1 - \alpha a_0$ であったから \begin{align*} \frac{a_{n}}{\alpha^n} = a_0 + \frac{a_1 - \alpha a_0}{\alpha} n \quad \therefore\; a_{n} = a_0\alpha^n + (a_1 - \alpha a_0)\alpha^{n-1} n \quad \therefore\; a_{n} = n\alpha^{n-1} a_1 + (1 - n)\alpha^n a_0 \;. \end{align*} この最終的な結果に、$\alpha = 0$ のときの一般項（$a_{n} = 0$）も含まれているところが興味深い。


(2) シフト演算子 $\hat{L}$ を使う方法

$a_{n+2} - 2\alpha a_{n+1} + \alpha^2 a_{n} = 0$ という３項間漸化式を、シフト演算子 $\hat{L}$ を使ってあらわすと \begin{align*} \hat{L}^2a_{n} - 2\alpha\hat{L}a_{n} + \alpha^2 a_{n} = (\hat{L}^2 - 2\alpha\hat{L} + \alpha^2) a_{n} = (\hat{L} - \alpha)(\hat{L} - \alpha)a_{n} = 0 \end{align*} である。$(\hat{L} - \alpha)a_{n}$ を満たす数列は「特殊解」のひとつで、それは $\alpha$ を公比とする等比数列であった。すなわち \begin{align*} a_{n} = \alpha a_{n-1} \quad\therefore\; a_{n} = \alpha^na_0 \end{align*} というような等比数列がひとつ求まるのだが、この数列は $a_0$ をきめれば決まってしまう。実際 $a_1 = \alpha a_0$ となっていて、$a_1$ には任意性がない。通常の３項間漸化式で定められる数列は、$a_0$ と $a_1$ に任意性があるので、今求めた数列は一般解ではないのである。つまり、そもそもの３項間漸化式をみたす数列は、この $a_{n} = \alpha a_0$ には限らないのである（第２章 シフト演算子を使って解くのところで同様の考察をした）。

重根を持たない場合であれば、２つの特殊解の線型結合から一般解が得られたが、重根の場合は特殊解もひとつしか得られないので、線型結合しても意味がない（というか、そもそも線型結合の意味がない）。したがってこの方法ではここまで、なのである。


(3) 行列と固有値方程式を使う方法

$a_{n+2} - 2\alpha a_{n+1} + \alpha^2 a_{n} = 0$ という３項間漸化式を、行列を使ってあらわすと \begin{align*} \begin{pmatrix} a_{n+2} \\ a_{n+1} \end{pmatrix} = \begin{pmatrix} 2\alpha & -\alpha^2 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} a_{n+1} \\ a_{n} \end{pmatrix} \end{align*} であるから、一般項は \begin{align*} \begin{pmatrix} a_{n+2} \\ a_{n+1} \end{pmatrix} = \begin{pmatrix} 2\alpha & -\alpha^2 \\ 1 & 0 \end{pmatrix}^{n+1} \begin{pmatrix} a_1 \\ a_0 \end{pmatrix} \end{align*} という風にあらわせて、問題は行列の冪乗を求めることに移った。そしてそのために、固有値方程式をたてて固有値をもとめ、それをもとに行列の対角化を試みるという方法を採用したのであった。さて、この方法が、重根の場合うまくいくだろうか？とりあえず、重根でない場合と同様な道筋で考えを進めていってみる（なおちなみに、固有値方程式の世界では、重根になることを「固有値が縮退している」という言葉使いをすることが多い。本来ならば異なっていて欲しい固有値が同一のものに縮退してしまっている、といった感慨を表しているのだと思う）。

さてこの場合、固有値方程式をたてて得られる特性方程式は、固有値を $\lambda$ であらわすと \begin{align*} \det\left\{ \begin{pmatrix} 2\alpha & -\alpha^2 \\ 1 & 0 \end{pmatrix} - \lambda \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \right\} = \det \begin{pmatrix} 2\alpha - \lambda & -\alpha^2 \\ 1 & - \lambda \end{pmatrix} = 0 \end{align*} となる。行列式の計算を実践すると \begin{align*} \lambda^2 - 2\alpha\lambda + \alpha^2 = (\lambda - \alpha)^2 = 0 \end{align*} となっていて、確かに（本来２つあって欲しい）固有値 $\lambda$ がひとつ $\lambda = \alpha$ に縮退していることがわかる。そしてこの固有値に対応する固有ベクトル $\vec{v} = \begin{pmatrix} x \\ y \end{pmatrix}$ は \begin{align*} \begin{pmatrix} 2\alpha & -\alpha^2 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = \alpha \begin{pmatrix} x \\ y \end{pmatrix} \quad\therefore\; \begin{pmatrix} \alpha & -\alpha^2 \\ 1 & -\alpha \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix} \quad\therefore\; \begin{cases} \, \alpha(x - \alpha y) = 0 \\ \, x - \alpha y = 0 \end{cases} \end{align*} を満たすものとなる。この結果から固有ベクトルの代表的なものとして、$\vec{v} = \begin{pmatrix} \alpha \\ 1\end{pmatrix}$ を選んで \begin{align*} \mat{P} = \begin{pmatrix} \vec{v} & \vec{v} \end{pmatrix} = \begin{pmatrix} \alpha & \alpha \\ 1 & 1 \end{pmatrix} \end{align*} という行列を作る。その上で固有値が縮退していないときと同様の論法を適用してみると \begin{align*} \begin{pmatrix} 2\alpha & -\alpha^2 \\ 1 & 0 \end{pmatrix} \mat{P} = \begin{pmatrix} 2\alpha & -\alpha^2 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} \alpha & \alpha \\ 1 & 1 \end{pmatrix} = \begin{pmatrix} \alpha^2 & \alpha^2 \\ \alpha & \alpha \end{pmatrix} = \begin{pmatrix} \alpha & \alpha \\ 1 & 1 \end{pmatrix} \begin{pmatrix} \alpha & 0 \\ 0 & \alpha \end{pmatrix} = \mat{P} \begin{pmatrix} \alpha & 0 \\ 0 & \alpha \end{pmatrix} \end{align*} となって、対角化に成功したように見える。しかしながらそうは甘くない。上の結果に対して、右側から $\mat{P}^{-1}$ をかければ首尾良くなるのだが、じつはこの $\mat{P}$ は、行列式が $0$ となっている。つまり正則ではない。それゆえ逆行列を持たないのである。したがって $\mat{P}^{-1}$ を右側から掛けるという処方は使えない。さらにいえば、この理路では、上のシフト演算子を利用した論法で出てきた特殊解も導けない。なので、重根の場合は、この論法で一般項を求めるのは諦めた方が良いのである。


$\blacksquare$ $a_{n+2} = 6 a_{n+1} - 9 a_{n}$ の一般項をもとめるエクササイズ

\begin{align*} a_{n+2} = 6 a_{n+1} - 9 a_{n} \iff a_{n+2} - 6 a_{n+1} + 9 a_{n} = 0 \end{align*} であるから、特性方程式をとけば、 \begin{align*} x^2 - 6x + 9 = (x - 3)^2 = 0 \quad\therefore\; \alpha = \beta = 3 \;. \end{align*} となって、この特性方程式は重根をもつ。したがって(1)の解法を用いるしかなく、その結果一般項は \begin{align*} a_{n} = n3^{n-1}a_1 + (1 - n)3^{n} a_0 \end{align*} となる。$a_0,\, a_1$ を決めれば具体的な数列が決まって、たとえば \begin{alignat*}{2} & a_0 = 0, a_1 =1 \;\text{のときは}\; a_n = n3^{n-1} & &\quad\text{i.e.}\; (a_n) = (0, 1, 6, 27, 108, \ldots) \\ & a_0 = 1, a_1 =1 \;\text{のときは}\; a_n = n3^{n-1} + (1 - n)3^{n} & &\quad\text{i.e.}\; (a_n) = (1, 1, -3, -27, -135, \ldots) \end{alignat*} である。


$\blacksquare$ ３項間漸化式が定数項を持ち、かつ、その特性方程式が重根を持つ場合

第４章 定数項のある３項間漸化式の場合で定数項のある場合を考えた。それにならって、特性方程式が重根を持つときで定数項のある場合も考えておく。すなわち \begin{align*} a_{n+2} = 2\alpha a_{n+1} - \alpha^2 a_{n} + r \;\iff\; a_{n+2} - 2\alpha a_{n+1} + \alpha^2 a_{n} = ｒ \end{align*} という形の３項間漸化式を考えるのである。これは、表題に述べたように、定数項を持ち、特性方程式が重根を持つ場合の３項間漸化式だ。

第４章では、特性方程式を用いる解法で２通りのものがあることをみた。まずその解法１と同じ様に定数項をなくしてみる。$a_{n} = a^{\prime}_{n} + s$ とすると、この漸化式は \begin{align*} & (a^{\prime}_{n+2} + s) - 2\alpha(a^{\prime}_{n+1} + s) + \alpha^2(a^{\prime}_{n} + s) = ｒ \\ &\therefore\; a^{\prime}_{n+2} - 2\alpha a^{\prime}_{n+1} + \alpha^2 a^{\prime}_{n} +(s - 2\alpha s + \alpha^2s - r) = 0 \end{align*} となるから、 \begin{align*} s - 2\alpha s + \alpha^2s - r = 0 \iff s = \frac{r}{\alpha^2 - 2\alpha + 1} = \frac{r}{(\alpha - 1)^2} \end{align*} となる $s$ を選べば、定数項のない３項間漸化式 $a^{\prime}_{n+2} - 2\alpha a^{\prime}_{n+1} + \alpha^2 a^{\prime}_{n} = 0$ に変形できるので、あとはこれを解けば良いことになる。上の $s$ の形からわかるように、$\alpha = 1$ のときは $s$ は決まらない。そこではて、となりそうだが、そもそも $\alpha= 1$ であるならば漸化式は \begin{align*} a_{n+2} - 2\alpha a_{n+1} + \alpha^2 a_{n} = ｒ \iff a_{n+2} - 2a_{n+1} + a_{n} = ｒ \iff (a_{n+2} - a_{n+1}) = (a_{n+1} - a_{n}) + ｒ \end{align*} となって、定数項のある２項間漸化式であり、この場合は等差数列になっているので、それを解けばよいのである（心配ならば、$b_{n} = a_{n+1} - a_{n}$ と起き直してみれば良い）。

解法２もほぼ同様である。 \begin{align*} a_{n+2} - 2\alpha a_{n+1} + \alpha^2 a_{n} = ｒ \iff (a_{n+2} - \alpha a_{n+1}) - \alpha(a_{n+1} - \alpha a_{n}) = ｒ \end{align*} というように、やはり定数項のある２項間漸化式に帰着する（これも心配ならば、$b_{n} = a_{n+1} - \alpha a_{n}$ と起き直してみれば良い）。したがって解くべき対象はこの２項間漸化式になるのである。

補遺２ ２項間漸化式をめぐって

$\blacksquare$ ２項間漸化式の形態

普通に健康的な２項間漸化式は、$p,\, q$ をただの数として

  1. $a_{n+1} = p a_{n}$
  2. $a_{n+1} = p a_{n} + q$
  3. $a_{n+1} = p a_{n} + f(n)$（$f(n)$ は $n$ を変数とする何らかの関数）
という３種類に大別できる。

このうち、1. は明らかに公比 $p$ の等比数列であるから一般項は瞬時にもとまって $a_{n} = p^n a_0$ である。ひとつ飛んで 3. は、関数 $f(n)$ の形次第でさまざまな解き方があり、場合によっては解けないものもある。なので、汎用的な解法を考えるのは困難である。残った 2. の形式は、定数項がある２項間漸化式となっている。そしてこの形式の数列には、一般項を求める汎用的な解法がある。これからそれを見ていく。


$\blacksquare$ 定数項のある２項間漸化式の解法

$\square$ 単純に定数項をなくす方法

項がひとつずれた漸化式を並べて書くと \begin{align*} & a_{n+2} = p a_{n+1} + q \\ & a_{n+1} = p a_{n} + q \end{align*} となるので、この２式を引き算すると \begin{align*} a_{n+2} - a_{n+1} = p (a_{n+1} - a_{n}) \end{align*} という公比 $p$ の等比数列の漸化式が得られる（高校数学の言葉で言えば、階差数列が公比 $p$ の等比数列になっている）。したがってその等比数列の一般項は \begin{align*} a_{n+1} - a_{n} = p^n (a_1 - a_0) \end{align*} である。この式には $n$ に依存する数列項が２つあるので、それをひとつにすることを考える。といってもそれは明解で、そもそもの漸化式 $a_{n+1} = p a_{n} + q$ をあてはめることにより \begin{align*} (p a_{n} + q) - a_{n} = p^n (a_1 - a_0) \quad\therefore\; (p - 1)a_{n} = p^n (a_1 - a_0) - q \end{align*} となる。また、$a_1 = p a_0 + q$ も利用すれば \begin{align*} (p - 1)a_{n} = p^n \{(p a_0 + q) - a_0\} - q \quad\therefore\; (p - 1)a_{n} = p^n \{(p - 1)a_0 + q\} - q \;. \end{align*} ここで「割り算」をしたいので、場合分けをする。$p \neq 1$ のときは \begin{align*} a_{n} = \frac{p^n \{(p - 1)a_0 + q\} - q}{p - 1} \quad\therefore\; a_{n} = p^n \left(a_0 + \frac{q}{p - 1}\right) - \frac{q}{p - 1} = p^n a_0 + \left(\frac{p^n - 1}{p - 1}\right)q \;. \end{align*} では、$p = 1$ のときはどうなのか？そもそもの漸化式にに立ち戻ればそれは $a_{n+1} = a_{n} + q$ となって、これは公差 $d$ の等差数列である。したがって一般項は造作なく求められ、$a_{n} = a_0 + nq$ である。

$a_{n+1} - a_{n} = p^n (a_1 - a_0)$ から一般項を求める方法にこのようなものもある（高校の教室でなされた方法を今思い出した）。 $n$ を繰り下げていき、その際の各式を縦に並べると \begin{align*} a_{n} - a_{n-1} &= p^{n-1} (a_1 - a_0) \\ a_{n-1} - a_{n-2} &= p^{n-2} (a_1 - a_0) \\ \cdots &= \cdots \\ a_{2} - a_{1} &= p^1 (a_1 - a_0) \\ a_{1} - a_{0} &= p^0 (a_1 - a_0) \end{align*} となるので、これらを足し合わせると、左辺の中間部分が相殺されて \begin{align*} a_{n} - a_0 = (p^{n-1} + p^{n-2} + \cdots + p + 1) (a_1 - a_0) \end{align*} となる。右辺の $p$ の冪乗からなる多項式は、公比 $p$ の等比数列の和（級数）である。それを $S$ として、さらに $pS$ を計算して並べてみると \begin{alignat*}{2} pS &= p^n + & & p^{n-1} + p^{n-2} + \cdots + p \\ S &= & & p^{n-1} + p^{n-2} + \cdots + p + 1 \end{alignat*} である。引き算して、$p \neq 1$ のとき \begin{alignat*}{2} (p - 1)S = p^n - 1 \quad\therefore\; S = \frac{p^n - 1}{p - 1} \end{alignat*} となって、 \begin{align*} a_{n} - a_0 = (p^{n-1} + p^{n-2} + \cdots + p + 1) (a_1 - a_0) = \frac{p^n - 1}{p - 1}(a_1 - a_0) \;. \end{align*} $a_1 = p a_0 + q$ を使って整理すれば \begin{align*} a_{n} = \frac{p^n - 1}{p - 1}\{(p - 1) a_0 + q\} + a_0 = p^n a_0 + \left(\frac{p^n - 1}{p - 1} q\right) \;. \end{align*} 当然同じ結果である。

$\square$ 特性方程式を用いる方法

定数項をなくす方法にもうひとつ別のやり方がある。「分割分配」することを考えるのである。まず天下り的であるが、$q = \alpha - p\alpha$ となる $\alpha$ を考えれば \begin{align} a_{n+1} = p a_{n} + q \iff a_{n+1} = p a_{n} + \alpha - p\alpha \iff a_{n+1} - \alpha = p (a_{n} - \alpha) \label{2t1.01} \end{align} というように等比数列が導きだせる。この $\alpha$ は $q = \alpha - p\alpha$ という関係を満たすものとして導入したので \begin{align*} q = \alpha - p\alpha \iff \alpha - p\alpha - q = 0 \end{align*} と変形できる。この天下り的に導入した $\alpha$ であるけれども、方程式の精神を尊重すると、$\alpha$ は方程式 $x - px - q = 0$ の解である、というように見立てることが可能である。そしてこの方程式を２項間漸化式の特性方程式と呼ぶならわしである。したがって、ことばの定義でもあるが \begin{align*} \text{２項間漸化式}\;&:\; a_{n+1} - p a_{n} - q = 0 \\ \text{特性方程式}\;&:\; x - p x - q = 0 \end{align*} と関係づけられることになる。$p \neq 1$ のときには $x = q/(1-p)$ であるから、これを $\alpha$ として、等比数列 $(a_{n} - \alpha)$ の一般項を求め、最後に $(a_{n})$ の一般項を求めれば良い。実際、\eqref{2t1.01}から $a_{n} - \alpha = p^n(a_0 - \alpha)$ であるので、求めた $\alpha$ を代入すると \begin{align*} a_{n} - \frac{q}{1-p} = p^n\left(a_0 - \frac{q}{1-p}\right) \quad\therefore\; a_{n} = p^n a_0 + \left(\frac{p^n - 1}{p-1}\right)q \end{align*} となる。

今の結果からあきらかなように、$p \neq 1$ のときは、この方法でも $(a_{n})$ の一般項も求まる。$p = 1$ のときは、特性方程式だけみていると、解としての $x$ にはすべての数が許されるからその先に進みようがないというのが第一感であるが、上の「単純に定数項をなくす方法」で見たように、そもそもの漸化式が等差数列になるのでその一般項は簡単にもとまる。なのでわざわざ特製方程式を持ち出すまでもない。

以上の２つの解法をみてみると、特製方程式を利用する方が計算がシステマティックになると感じられる。

あとがき

特性方程式、シフト演算子、行列の対角化、という３通りの方法で３項間漸化式を解いてみた。ここでみたように、この形式、つまり $a_{n+2} = p a_{n+1} + q a_{n}$ という形式の３項間漸化式は、$p$ と $q$ がともに $n$ に依存しないただの数であれば、一般項が求められるのである。

本文からもあきらかであると思うが、特性方程式が重根を持たない場合、別の言い方をすれば固有値方程式の固有値が縮退していない場合は、シフト演算子 $\hat{L}$ を使う方法がもっともやさしいと思う。やさしいというより、筆算の量が少ないというべきか。それに比べて、固有値方程式から行列の対角化を利用する方法は筆算量が大である。しかし、このやり方であれば、３項間に限らず $N$ 項間の漸化式でもやり方は変わらないので、システマティックにおこなえる。とはいえ、固有値方程式を解くにはそれなりに相当の手間がいりそうではあるが。いきなり特性方程式から入る解法（高校数学的解法）は、半分判じものであるという気がする。

やはりもっとも簡単なのは、再帰構造のプログラムを書いて動かす方法だろう。計算機は偉大である。

ちなみに、シフト演算子 $\hat{L}$ を使う方法では、線型性が大きく物を言っている。行列と固有値方程式の方法では、そもそもの行列表現で一般項がもとまっていると見なすこともできる。行列表現を離れた具体的な一般項は対角化によって求められるが、そこで問題を解くためには、定数倍の任意性のある固有ベクトル（これも線型性のあらわれである）から代表的なものをえらぶという操作が、なんとなく面映い。ここでハードルが幾分上がっているかもしれない。

しかし html では、この長さの文章は読むのが苦痛である。mathjax のロードに時間もかかるし、画面の幅で数式の印象も変わってしまう。これからは、もうすべて tex -> pdf でいった方がいいと思った。あ、roff もありか。