三項間漸化式と行列の固有値
概要
三項間漸化式と行列の固有値（linear recurrences and eigenvalues）とは、三項間漸化式 $a_{n+2}=pa_{n+1}+qa_n$（$q\ne0$）の特性方程式 $t^2=pt+q$ を、行列 $C=\begin{pmatrix}p&q\\1&0\end{pmatrix}$ の固有値の方程式として見直す見方である。$v_n=(a_{n+1},a_n)^{\top}$ は $v_{n+1}=Cv_n$ を満たし、異なる 2 解なら $C$ は対角化でき、一般項は $A\alpha^n+B\beta^n$、重解なら対角化できず Jordan 細胞で $(A+Bn)\alpha^n$ が現れる。$C^n$ は $t^n$ を固有多項式で割った余りからも求まる。
三項間漸化式と特性方程式
高校では、2 つ前までの項から次の項が決まる数列の一般項を、特性方程式を使って求める。この記事は、その方法を大学の線形代数（行列の固有値）の言葉で見直す 4 本の記事への案内である。まず主題の定義と、代表的な計算を 1 つずつ見る。そのあと、出発点になる 2 つの事実（異なる 2 解のときの一般項、特性方程式の解が行列の固有値であること）をこの記事の中で証明する。
複素数の定数 $p,q$（$q\ne0$）について、すべての $n\ge0$ で
$$
a_{n+2}=pa_{n+1}+qa_n
$$
を満たす数列 $(a_n)$ を、この三項間漸化式の解という。$t$ の 2 次方程式 $t^2=pt+q$ を、この漸化式の特性方程式という。
解は、初期値 $a_0,a_1$ を決めると 1 通りに決まる（漸化式で $a_2,a_3,\dots$ が順に 1 つずつ決まるから）。等比数列 $\lambda^n$（$\lambda\ne0$）が解になるのは、$\lambda$ が特性方程式の解のときに限る。実際、$a_n=\lambda^n$ を代入すると漸化式は $\lambda^{n+2}=p\lambda^{n+1}+q\lambda^n$ となり、両辺を $\lambda^n\ne0$ で割ると $\lambda^2=p\lambda+q$ になる。逆に $\lambda^2=p\lambda+q$ なら、両辺に $\lambda^n$ を掛けて漸化式が得られる。
$a_0=0$、$a_1=4$、$a_{n+2}=2a_{n+1}+3a_n$ とする。項は $0,4,8,28,80,244,\dots$ である。特性方程式 $t^2=2t+3$ の解は $3,-1$ で、数列 $a_{n+1}+a_n$ は公比 $3$、数列 $a_{n+1}-3a_n$ は公比 $-1$ の等比数列になる。
$$
a_{n+1}+a_n=4\cdot3^n,\qquad a_{n+1}-3a_n=4\cdot(-1)^n
$$
の上の式から下の式を引いて $4a_n=4\cdot3^n-4\cdot(-1)^n$、すなわち $a_n=3^n-(-1)^n$ を得る。$n=5$ で $243+1=244$ である。
この例の計算は、特性方程式が異なる 2 解をもつときにはいつでも使える。
特性方程式 $t^2=pt+q$ が異なる 2 解 $\alpha,\beta$ をもつとする。このとき、漸化式 $a_{n+2}=pa_{n+1}+qa_n$ の解は、すべての $n\ge0$ で
$$
a_n=\frac{(a_1-\beta a_0)\alpha^n-(a_1-\alpha a_0)\beta^n}{\alpha-\beta}
$$
を満たす。とくに、解は定数 $A,B$ を使って $a_n=A\alpha^n+B\beta^n$ と書ける。
方針：ex-lre-distinct と同じく、$a_{n+1}-\beta a_n$ と $a_{n+1}-\alpha a_n$ が等比数列になることを示し、2 つの式から $a_{n+1}$ を消す。
段 1（解と係数の関係）。$\alpha,\beta$ は $t^2-pt-q=0$ の 2 解なので、$t^2-pt-q=(t-\alpha)(t-\beta)$ であり、係数を比べて $\alpha+\beta=p$、$\alpha\beta=-q$ である。
段 2（等比数列を作る）。段 1 を漸化式に代入すると
$$
a_{n+2}=(\alpha+\beta)a_{n+1}-\alpha\beta a_n
$$
である。$\beta a_{n+1}$ を左辺に移して整理すると
$$
a_{n+2}-\beta a_{n+1}=\alpha a_{n+1}-\alpha\beta a_n=\alpha\bigl(a_{n+1}-\beta a_n\bigr)
$$
となる。よって $b_n:=a_{n+1}-\beta a_n$ は $b_{n+1}=\alpha b_n$ を満たし、公比 $\alpha$ の等比数列であるから、$b_n=\alpha^nb_0=\alpha^n(a_1-\beta a_0)$ である。$\alpha$ と $\beta$ の役を入れかえた同じ計算で、$a_{n+1}-\alpha a_n=\beta^n(a_1-\alpha a_0)$ である。
段 3（$a_{n+1}$ を消す）。段 2 の 2 つの式
$$
a_{n+1}-\beta a_n=\alpha^n(a_1-\beta a_0),\qquad a_{n+1}-\alpha a_n=\beta^n(a_1-\alpha a_0)
$$
の上から下を引くと、左辺は $(\alpha-\beta)a_n$ になる。$\alpha\ne\beta$ なので $\alpha-\beta$ で割ることができ、示したい式を得る。$A=\frac{a_1-\beta a_0}{\alpha-\beta}$、$B=-\frac{a_1-\alpha a_0}{\alpha-\beta}$ とおけば $a_n=A\alpha^n+B\beta^n$ である。$\square$
ex-lre-distinct では $\alpha=3$、$\beta=-1$、$a_0=0$、$a_1=4$ なので、$A=\frac{4-0}{4}=1$、$B=-\frac{4-0}4=-1$ となり、$a_n=3^n-(-1)^n$ と一致する。段 3 で $\alpha-\beta$ で割ったところが、重解のときには使えない。そのとき何が起きるかを次の例で見る。
$a_0=1$、$a_1=4$、$a_{n+2}=4a_{n+1}-4a_n$ とする。特性方程式 $t^2-4t+4=(t-2)^2=0$ は重解 $2$ をもつ。$a_{n+1}-2a_n=2^{n+1}$ の両辺を $2^{n+1}$ で割ると $\frac{a_{n+1}}{2^{n+1}}-\frac{a_n}{2^n}=1$ なので、$\frac{a_n}{2^n}$ は公差 $1$ の等差数列であり、$a_n=(n+1)2^n$（$1,4,12,32,80,\dots$）となる。一般項に $n$ が掛かる。
$a_0=0$、$a_1=1$、$a_{n+2}=a_{n+1}-a_n$ とする。順に計算すると $a_2=1-0=1$、$a_3=1-1=0$、$a_4=0-1=-1$、$a_5=-1-0=-1$、$a_6=-1-(-1)=0$、$a_7=0-(-1)=1$ で、$0,1,1,0,-1,-1$ の 6 項がくり返す。特性方程式 $t^2-t+1=0$ の判別式は $1-4=-3<0$ で、解は虚数 $\frac{1\pm\sqrt3\,i}2$ である。
特性方程式の解が異なる実数・虚数・重解の 3 つの例のふるまい
図 1 は 3 つの例のふるまいである。左は ex-lre-distinct の $a_n$ を $3^n$ で割った値で、$1-(-\frac13)^n$ となって $1$ に近づく。中央は ex-lre-complex の $a_n$ で、周期 6 でくり返す。右は ex-lre-double の $a_n$ を $2^n$ で割った値で、$n+1$ と一直線に増え続ける。
解の種類（異なる実数解・虚数解・重解）で分かれるのは、一般項の形である。数列のふるまいは、解の種類だけでは決まらない。解の絶対値や初期値にもよる。たとえば解が虚数でも、周期的になるとは限らない。中央の例が周期的なのは、解の絶対値が $1$ で、6 乗すると $1$ になるからである（三項間漸化式の特性方程式）。
ex-lre-distinct の漸化式は、隣り合う 2 項を縦に並べた $v_n:=\begin{pmatrix}a_{n+1}\\a_n\end{pmatrix}$ を使うと
$$
v_{n+1}=\begin{pmatrix}2&3\\1&0\end{pmatrix}v_n,\qquad\text{たとえば}\quad \begin{pmatrix}8\\4\end{pmatrix}=\begin{pmatrix}2\cdot4+3\cdot0\\4\end{pmatrix}
$$
と書ける。この行列 $C=\begin{pmatrix}2&3\\1&0\end{pmatrix}$ は、ベクトル $\begin{pmatrix}3\\1\end{pmatrix}$ を $3$ 倍の $\begin{pmatrix}9\\3\end{pmatrix}$ に、$\begin{pmatrix}-1\\1\end{pmatrix}$ を $-1$ 倍の $\begin{pmatrix}1\\-1\end{pmatrix}$ に写す。$3$ と $-1$ は特性方程式の解である。
2 次の正方行列 $C$ と数 $\lambda$ について、$\mathbf 0$ でないベクトル $v$ で $Cv=\lambda v$ を満たすものがあるとき、$\lambda$ を $C$ の固有値、$v$ を固有値 $\lambda$ に対する固有ベクトルという。
固有ベクトルは、行列 $C$ を掛けても同じ直線の上にとどまる（定数倍になる）ベクトルであり、固有値はその倍率である。倍率は負でもよく（向きが反対になる）、虚数でもよい（そのときはベクトルの成分も複素数にする）。ex-lre-matrix の $3$ と $-1$ は $C$ の固有値である。一般に次が成り立つ。これが 4 本の記事を貫く見方である。
$C=\begin{pmatrix}p&q\\1&0\end{pmatrix}$ とする。数 $\lambda$ が $C$ の固有値であるための必要十分条件は、$\lambda$ が特性方程式 $t^2=pt+q$ の解であることである。このとき $\begin{pmatrix}\lambda\\1\end{pmatrix}$ は固有値 $\lambda$ に対する固有ベクトルである。
段 1（成分で書く）。$v=\begin{pmatrix}x\\y\end{pmatrix}$ とすると $Cv=\begin{pmatrix}px+qy\\x\end{pmatrix}$ なので、$Cv=\lambda v$ は 2 つの式
$$
px+qy=\lambda x,\qquad x=\lambda y
$$
と同じである。
段 2（固有値なら特性方程式の解）。$\lambda$ が固有値で、$v\ne\mathbf 0$ が $Cv=\lambda v$ を満たすとする。段 1 の 2 つ目の式から $x=\lambda y$ である。もし $y=0$ なら $x=\lambda\cdot0=0$ となり $v=\mathbf 0$ に反するので、$y\ne0$ である。1 つ目の式に $x=\lambda y$ を代入すると $p\lambda y+qy=\lambda^2y$ で、両辺を $y\ne0$ で割って $\lambda^2=p\lambda+q$ を得る。
段 3（特性方程式の解なら固有値）。$\lambda^2=p\lambda+q$ とし、$v=\begin{pmatrix}\lambda\\1\end{pmatrix}$ とおく。$v$ の第 2 成分は $1$ なので $v\ne\mathbf 0$ であり、
$$
Cv=\begin{pmatrix}p\lambda+q\\\lambda\end{pmatrix}=\begin{pmatrix}\lambda^2\\\lambda\end{pmatrix}=\lambda\begin{pmatrix}\lambda\\1\end{pmatrix}=\lambda v
$$
である。よって $\lambda$ は固有値で、$v$ はその固有ベクトルである。$\square$
ex-lre-matrix の固有ベクトル $\begin{pmatrix}3\\1\end{pmatrix}$、$\begin{pmatrix}-1\\1\end{pmatrix}$ は、ちょうど段 3 の $\begin{pmatrix}\lambda\\1\end{pmatrix}$ の形をしている。等比数列の解 $a_n=\lambda^n$ から作った $v_n=\begin{pmatrix}\lambda^{n+1}\\\lambda^n\end{pmatrix}=\lambda^n\begin{pmatrix}\lambda\\1\end{pmatrix}$ が固有ベクトルの定数倍であることも、この形から分かる。
反例：解の種類とふるまい
thm-lre-distinct と prop-lre-eigen には条件が付いていた。条件を外したときや、「解の種類だけでふるまいが決まる」と思い込んだときに崩れる例を表にまとめる。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 特性方程式の 2 解が異なる（thm-lre-distinct） | $a_{n+2}=4a_{n+1}-4a_n$、$a_0=1$、$a_1=4$（重解 $2$） | 一般項が $A\cdot2^n+B\cdot2^n$ の形で書けない |
| 解の絶対値が $1$ で、ある冪が $1$ になる | $a_{n+2}=2a_{n+1}-2a_n$、$a_0=0$、$a_1=1$（解 $1\pm i$） | 解が虚数なのに周期的でない |
| 固有ベクトルは $\mathbf 0$ でない（def-lre-eigen） | $v=\mathbf 0$ | どんな $\lambda$ でも $C\mathbf 0=\lambda\mathbf 0$ となり、固有値が決まらない |
ex-lre-double の数列 $1,4,12,32,\dots$ を $A\cdot2^n+B\cdot2^n=(A+B)2^n$ と書けたとすると、$n=0$ から $A+B=1$、$n=1$ から $2(A+B)=4$ すなわち $A+B=2$ となって矛盾する。重解のときは等比数列が 1 種類しか取れず、prf-thm-lre-distinct の段 3 の「$\alpha-\beta$ で割る」ができない。実際の一般項は $(n+1)2^n$ で、$n$ が掛かった項が必要になる。
$a_0=0$、$a_1=1$、$a_{n+2}=2a_{n+1}-2a_n$ とする。特性方程式 $t^2-2t+2=0$ の解は $1\pm i$ で虚数である。項を順に計算すると
$$
0,\ 1,\ 2,\ 2,\ 0,\ -4,\ -8,\ -8,\ 0,\ 16,\ \dots
$$
で、$4$ 項ごとに $0$ が現れるが、そのあいだの項の絶対値は $1,2,2$、$4,8,8$、$16,\dots$ と $4$ 倍ずつになり、周期的にはならない。解の絶対値が $|1\pm i|=\sqrt2>1$ で、$(1\pm i)^4=-4$ だからである。ex-lre-complex の数列が周期 6 でくり返したのは、解の絶対値が $1$ で 6 乗すると $1$ になるという、解の種類とは別の条件のおかげである。
高校の計算と大学の概念
| 高校の計算 | 大学の概念 | 記事 |
|---|---|---|
| 等比数列 $\lambda^n$ が解になる条件 $\lambda^2=p\lambda+q$（特性方程式） | 行列 $C$ の固有値の方程式（固有多項式を $0$ とおいた方程式） | 三項間漸化式の特性方程式、漸化式の行列表示 |
| $a_{n+1}-\beta a_n$ が公比 $\alpha$ の等比数列 | 左固有ベクトルによる成分の取り出し | 漸化式の行列表示 |
| 一般項 $A\alpha^n+B\beta^n$ | コンパニオン行列の対角化 $C^n=PD^nP^{-1}$ | 漸化式の行列表示 |
| 重解で一般項が $(A+Bn)\alpha^n$ | 対角化できない行列と Jordan 細胞 | 重解とJordan細胞 |
| $x^n$ を 2 次式で割った余り | Cayley–Hamilton の定理と $C^n=r_nC+s_nE$ | 行列のn乗と割り算の余り |
読む順番
- 三項間漸化式の特性方程式：行列を使わず、高校の道具（等比数列・等差数列・解と係数の関係）だけで、特性方程式による解き方がなぜ正しいかを証明する。解が虚数のときの周期的な数列や、数学オリンピックの問題（国際数学オリンピック（1976 年）第 6 問）も扱う。
- 漸化式の行列表示：漸化式を $v_{n+1}=Cv_n$ と書き、特性方程式がコンパニオン行列 $C$ の固有多項式であることを示す。異なる 2 解なら $C$ が対角化でき、一般項が出ることを見る。行列の積から説明するので、行列を習っていなくても読める。
- 重解とJordan細胞：重解のとき $C$ が対角化できないことを示し、Jordan 細胞 $\begin{pmatrix}\alpha&1\\0&\alpha\end{pmatrix}$ の $n$ 乗から $n\alpha^{n-1}$ が現れることを見る。「一般項に $n$ が掛かる理由」への答えである。
- 行列のn乗と割り算の余り：2 次の Cayley–Hamilton の定理を証明し、$C^n$ を「$t^n$ を固有多項式で割った余り」から求める。Fibonacci 数の行列の冪や、$(1+\sqrt2)^n$ が整数に近づく理由も扱う。
1 だけ読めば高校の計算の根拠が分かる。2 は 3・4 の前提である。3 と 4 はどちらを先に読んでもよい。
疑問から記事を探すときは、次の表を使うとよい。疑問 答えのある記事 なぜ等比数列 $\lambda^n$ を代入すると特性方程式が出るのか 三項間漸化式の特性方程式 $a_{n+1}-\beta a_n$ を考えるとうまくいくのはなぜか 三項間漸化式の特性方程式、漸化式の行列表示 特性方程式は、行列のどんな性質を表しているのか 漸化式の行列表示 重解のとき、一般項に $n$ が掛かるのはなぜか 重解とJordan細胞 行列の $n$ 乗を、掛け算をくり返さずに求められるか 行列のn乗と割り算の余り $(1+\sqrt2)^n$ がほとんど整数になるのはなぜか 行列のn乗と割り算の余り
関連する話題
同じ特性方程式は、微分方程式 $y''=py'+qy$ を解くときにも現れる。$e^{\lambda x}$ は微分すると $\lambda$ 倍になるので、等比数列 $\lambda^n$（1 つずらすと $\lambda$ 倍）の役を指数関数 $e^{\lambda x}$ がする。対応は次のとおりである。
| 漸化式 $a_{n+2}=pa_{n+1}+qa_n$ | 微分方程式 $y''=py'+qy$ |
|---|---|
| 1 つずらす：$a_n\mapsto a_{n+1}$ | 微分する：$y\mapsto y'$ |
| 等比数列 $\alpha^n$（ずらすと $\alpha$ 倍） | 指数関数 $e^{\alpha x}$（微分すると $\alpha$ 倍） |
| 一般項 $A\alpha^n+B\beta^n$、重解で $(A+Bn)\alpha^n$ | 一般解 $Ae^{\alpha x}+Be^{\beta x}$、重解で $(A+Bx)e^{\alpha x}$ |
| $v_n=(a_{n+1},a_n)^{\top}$ は $v_{n+1}=Cv_n$ | $Y=(y',y)^{\top}$ は $Y'=CY$ |
微分方程式の一般解の証明は 微分方程式としての指数関数・三角関数 にあり、行列で見る最後の行は 漸化式の行列表示 で触れる。微分方程式としての指数関数・三角関数 は方程式を $y''+py'+qy=0$ の形で書くので、ここでの $p,q$ はその記事の $-p,-q$ にあたる。また同記事では $p,q$ を実数とし、特性方程式の解が虚数のときは一般解を $\cos$ と $\sin$ で書いている。
- 数列を $\sum a_nx^n$ にまとめると、漸化式は分母 $1-px-qx^2$ の分数式になる（母関数：数列を関数として扱う）。
- $k$ 項前までを使う漸化式の一般論は 漸化式 の記事にある。
関連項目
- 前提: 数列, 等比数列, 2次方程式, 複素数
- 前に読む: 2次方程式の判別式の正体
- 次に読む: 三項間漸化式の特性方程式
- 関連（高校数学）: 確率漸化式と定常分布, 縮小写像と漸化式, Fibonacci数の母関数
- 各論: 三項間漸化式の特性方程式, 漸化式の行列表示, 重解とJordan細胞, 行列のn乗と割り算の余り
- 線形代数の側: 固有値, 固有多項式, 対角化, Jordan標準形, Cayley–Hamiltonの定理
- 比較: 漸化式, 微分方程式としての指数関数・三角関数, 母関数：数列を関数として扱う
- 例: Fibonacci数
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
