三項間漸化式と行列の固有値

同義語：三項間漸化式

概要

三項間漸化式と特性方程式

高校では、2 つ前までの項から次の項が決まる数列の一般項を、特性方程式を使って求める。この記事は、その方法を大学の線形代数（行列の固有値）の言葉で見直す 4 本の記事への案内である。まず主題の定義と、代表的な計算を 1 つずつ見る。

三項間漸化式とその特性方程式

複素数の定数 $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 通りに決まる。等比数列 $\lambda^n$（$\lambda\ne0$）が解になるのは、$\lambda$ が特性方程式の解のときに限る。

異なる 2 解の場合

$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$ である。

重解の場合

$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$ である。

図1：特性方程式の解が異なる実数・虚数・重解の 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$ は特性方程式の解である。

$\mathbf 0$ でないベクトルで、行列 $C$ を掛けても同じ直線の上にとどまる（定数倍になる）ものを $C$ の固有ベクトルといい、その倍率を $C$ の固有値という。倍率は負でもよく（向きが反対になる）、虚数でもよい。ex-lre-matrix の $3$ と $-1$ は $C$ の固有値である。特性方程式の解は、この行列の固有値である。これが 4 本の記事を貫く見方である。

高校の計算と大学の概念

高校の計算	大学の概念	記事
等比数列 $\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乗と割り算の余り

漸化式 $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$