Boda
記事一覧に戻る
2025/07/17

3項間漸化式を線形代数で解く

高校数学の問題である3項間漸化式の数列の問題を、線形代数の観点から考えます。

目次

目標

次の2つの問題を考えます。高校数学の典型的な問題です。

  1. a1=1, a2=1, an+2=5an+1−6ana_1 = 1,\, a_2 = 1,\, a_{n+2} = 5a_{n+1} - 6a_nを満たす数列{an}\{a_n\}の一般項を求めよ。
  2. b1=1, b2=3, bn+2=4bn+1−4bnb_1 = 1,\, b_2 = 3,\, b_{n+2} = 4b_{n+1} - 4b_nを満たす数列{bn}\{b_n\}の一般項を求めよ。

教科書通りに解くならば、特性方程式の解から漸化式を変形し、等比数列に帰着させることで一般項を求めるのでしょうが、計算がそこそこ煩雑です。答えだけ求めればよいのなら、次のように解くことができます。

  1. 特性方程式は、

    λ2−5λ+6=0 \gdef\va{\vec{\alpha}} \gdef\mat#1{\left[\begin{matrix} #1 \end{matrix}\right]} \gdef\dmat#1{\left|\begin{matrix} #1 \end{matrix}\right|} \lambda^2 - 5\lambda + 6 = 0

    である。これを解いてλ=2,3\lambda = 2,3なので、一般項は定数C1,C2C_1,C_2を用いて、

    an=C1 2n+C2 3n a_n = C_1\, 2^n + C_2\, 3^n

    と書ける。n=1,2n = 1,2とすると、定数が満たすべき条件は、

    {2C1+3C2=14C1+9C2=1 \begin{cases} 2C_1 + 3C_2 = 1\\ 4C_1 + 9C_2 = 1 \end{cases}

    なので、これを解いて、C1=1, C2=1/3C_1 = 1,\, C_2 = 1/3と定まる。以上から、数列{an}\{a_n\}の一般項は、

    an=2n+3n−1 a_n = 2^n + 3^{n-1}

  2. 特性方程式は、

    λ2−4λ+4=0 \lambda^2 - 4\lambda + 4 = 0

    である。これを解いてλ=2\lambda = 2なので、一般項はC1,C2C_1,C_2を用いて、

    bn=C1 2n+C2 n 2n b_n = C_1\, 2^n + C_2\, n\, 2^n

    と表せる。n=1,2n = 1,2とすると、定数が満たすべき条件は、

    {2C1+2C2=14C1+8C2=3 \begin{cases} 2C_1 + 2C_2 = 1\\ 4C_1 + 8C_2 = 3 \end{cases}

    なので、これを解いて、C1=1/4, C2=1/4C_1 = 1/4,\, C_2 = 1/4と定まる。以上から、数列{bn}\{b_n\}の一般項は、

    bn=2n−2(1+n) b_n = 2^{n-2} (1 + n)

解説

以上のような解法が正当化される理由を、行列・ベクトルの観点から考えましょう。 一般の場合を考えるため、数列{an}\{a_n\}について、はじめの2項a1,a2a_1,a_2、および漸化式

an+2=pan+1+qan(p≠0, q≠0) a_{n+2} = p a_{n+1} + q a_n \quad (p \neq 0,\, q \neq 0)

が与えられているとします。この漸化式は、行列とベクトルを用いて、

[an+2an+1]=[pq10][an+1an] \mat{a_{n+2} \\ a_{n+1}} = \mat{p & q \\ 1 & 0} \mat{a_{n+1} \\ a_n}

と書けるので、

A=[pq10],α⃗n=[an+1an] A = \mat{p & q \\ 1 & 0},\quad \va_n = \mat{a_{n+1} \\ a_n}

と定義すれば、α⃗n+1=Aα⃗n\va_{n+1} = A \va_nとなります。 したがって、行列AAを用いれば、α⃗n\va_nは、

α⃗n=An−1α⃗1 \va_n = A^{n-1} \va_1

と表せます。したがって、An−1A^{n-1}の行列要素を求めれば、ana_nが求まったことになります。 そこで、行列のべき乗を求めるため、AAを対角行列、あるいはジョルダン標準形へ相似変形することを考えます。このためにAAの固有値を求める必要がありますが、AAの固有方程式は、

(det⁡(A−λI)=∣p−λq1−λ∣=)λ2−pλ−q=0 \left(\det (A - \lambda I) = \dmat{p - \lambda & q \\ 1 & -\lambda} = \right) \lambda^2 - p \lambda - q = 0

であり、いわゆる「漸化式の特性方程式」と一致することがわかります。 以下では、この方程式の解の個数について場合分けをして考えます。

1. AAが対角化可能な(  ⟺  \iff特性方程式が重解をもたない)場合

漸化式の特性方程式が重解をもたない場合、AAは相異なる固有値を2つもち、 対角化可能です。すなわち、特性方程式λ2−pλ−q=0\lambda^2 - p \lambda - q = 0の2解をλ1,λ2\lambda_1,\lambda_2とすると、ある正則行列PPが存在して、

P−1AP=[λ100λ2] P^{-1} A P = \mat{\lambda_1 & 0 \\ 0 & \lambda_2}

が成立します。両辺をそれぞれn−1n-1乗すれば、

(左辺)n−1=(P−1AP)(P−1AP)⋯(P−1AP)=P−1An−1P(右辺)n−1=[λ100λ2]n−1=[λ1n−100λ2n−1] \begin{align*} (\text{左辺})^{n-1} &= (P^{-1} A P)(P^{-1} A P) \cdots (P^{-1} A P) = P^{-1} A^{n-1} P\\ (\text{右辺})^{n-1} &= \mat{\lambda_1 & 0 \\ 0 & \lambda_2}^{n-1} = \mat{\lambda_1^{n-1} & 0 \\ 0 & \lambda_2^{n-1}} \end{align*}

なので、左からPP、右からP−1P^{-1}をかければ、

An−1=P[λ1n−100λ2n−1]P−1 A^{n-1} = P \mat{\lambda_1^{n-1} & 0 \\ 0 & \lambda_2^{n-1}} P^{-1}

を得ます。したがってα⃗n\va_nは、

α⃗n=[an+1an]=P[λ1n−100λ2n−1]P−1[a2a2] \va_n = \mat{a_{n+1} \\ a_n} = P \mat{\lambda_1^{n-1} & 0 \\ 0 & \lambda_2^{n-1}} P^{-1} \mat{a_2 \\ a_2}

と表せるので、ana_nは適当な定数C~1,C~2\tilde{C}_1,\tilde{C}_2を用いて、

an=C~1λ1n−1+C~2λ2n−1 a_n = \tilde{C}_1 \lambda_1^{n-1} + \tilde{C}_2 \lambda_2^{n-1}

と書けます。新たに定数をC1=C1~/λ1, C2=C2~/λ2C_1 = \tilde{C_1} / \lambda_1,\, C_2 = \tilde{C_2} / \lambda_2と取り直せば、先の問題1.の解法で用いた一般項の表式

an=C1λ1n+C2λ2n a_n = C_1 \lambda_1^n + C_2 \lambda_2^n

を得ます。あとはa1,a2a_1,a_2の条件からC1,C2C_1,C_2を定めれば一般項が求まります。

2. AAが対角化不可能な(  ⟺  \iff特性方程式が重解をもつ)場合

漸化式の特性方程式が重解をもつ場合、AAの固有値は1つに縮退していて、 q≠0q \neq 0より対角化不可能です。このとき、特性方程式λ2−pλ−q=0\lambda^2 - p \lambda - q = 0の解をλ0\lambda_0とすると、ある正則行列PPが存在して、AAをジョルダン標準形

P−1AP=[λ010λ0] P^{-1} A P = \mat{\lambda_0 & 1 \\ 0 & \lambda_0}

に相似変換できます。

D=[λ000λ0],N=[0100] D = \mat{\lambda_0 & 0 \\ 0 & \lambda_0},\quad N = \mat{0 & 1 \\ 0 & 0}

と定義すると、P−1AP=D+NP^{-1} A P = D + Nと表せます。N2=ON^2 = O、すなわちNNを2乗以上すると零行列になることと、DN=NDDN = NDに注意すると、両辺をそれぞれn−1n-1乗して、

(左辺)n−1=(P−1AP)(P−1AP)⋯(P−1AP)=P−1An−1P(右辺)n−1=(D+N)n−1=Dn−1+(n−1)DN=[λ0n−1(n−1)λ00λ0n−1] \begin{align*} (\text{左辺})^{n-1} &= (P^{-1} A P)(P^{-1} A P) \cdots (P^{-1} A P) = P^{-1} A^{n-1} P\\ (\text{右辺})^{n-1} &= (D + N)^{n-1} = D^{n-1} + (n-1) D N = \mat{\lambda_0^{n-1} & (n-1) \lambda_0 \\ 0 & \lambda_0^{n-1}} \end{align*}

なので、左からPP、右からP−1P^{-1}をかければ、

An−1=P[λ0n−1(n−1)λ00λ0n−1]P−1 A^{n-1} = P \mat{\lambda_0^{n-1} & (n-1) \lambda_0 \\ 0 & \lambda_0^{n-1}} P^{-1}

を得ます。したがってα⃗n\va_nは

α⃗n=[an+1an]=P[λ0n−1(n−1)λ00λ0n−1]P−1[a2a2] \va_n = \mat{a_{n+1} \\ a_n} = P \mat{\lambda_0^{n-1} & (n-1) \lambda_0 \\ 0 & \lambda_0^{n-1}} P^{-1} \mat{a_2 \\ a_2}

と表せるので、ana_nは適当な定数C~1,C~2\tilde{C}_1,\tilde{C}_2を用いて、

an=C~1 λ0n−1+C~2 (n−1) λ0n−1 a_n = \tilde{C}_1\, \lambda_0^{n-1} + \tilde{C}_2\, (n-1)\, \lambda_0^{n-1}

と書けます。新たに定数をC1=(C1~−C~2)/λ0, C2=C2~/λ0C_1 = (\tilde{C_1} - \tilde{C}_2) / \lambda_0,\, C_2 = \tilde{C_2} / \lambda_0と取り直せば、先の問題2.の解法で用いた一般項の表式

an=C1 λ0n+C2 n λ0n a_n = C_1\, \lambda_0^n + C_2\, n\, \lambda_0^n

を得ます。あとはa1,a2a_1,a_2の条件からC1,C2C_1,C_2を定めれば一般項が求まります。