n項間の漸化式#1


$n$ 項間漸化式から数列の一般項を求める問題を考える.

$2$ 項間,$3$ 項間の漸化式の解法はよく知られているが,今回は線形代数(大学数学)を用いて

\[
a_{n+3} = p a_{n+2} + q a_{n+1} + r a_n + s \tag{$\diamondsuit$}
\]

の形の $4$ 項間漸化式を満たす数列 $\{a_n\}$ の一般項を求める.

スポンサーリンク
Question 1

漸化式
\[
a_{n+3} =-2a_{n+2} + a_{n+1} + 2a_n-1, \quad a_1 = 1 \quad a_2 = 2 \quad a_3 = 3
\]
で定められる数列 $\{a_n\} \quad (n=1,2,3,\ldots)$ の一般項を求めよ.

 

計算の方針と概略

定数部分(式 $(\diamondsuit)$ における $s$ )があるため,線形代数(行列)を用いた解法は例えば次の2通りが考えられる.

  • 定数項を含まない漸化式になるように数列を置き換える( $3$ 次行列の計算が必要)
  • 定数項を含んだ漸化式のまま解く( $4$ 次行列の計算が必要)
  • 今回は数列を置き換えて,扱う行列のサイズを小さくする方法をとる.計算の概略は以下の通り:

  • $b_{n} = a_{n+1}-a_{n}$ で定まる数列 $\{b_n\}$ が満たす漸化式を求める
  • ベクトル $\boldsymbol{x}_n$ を
    \[
    \boldsymbol{x}_n = \left[
    \begin{array}{c}
    b_{n+2} \\
    b_{n+1} \\
    b_n
    \end{array}
    \right]
    \]
    で定めて,$\boldsymbol{x}_{n+1} = A \boldsymbol{x}_n$ を満たす $3$ 次正方行列 $A$ を求める
  • $\boldsymbol{x}_n = A^{n-1}\boldsymbol{x}_1$ となることを利用するために $A^n$ を求める
  • $\{b_n\}$ の一般項を求める
  • $\{a_n\}$ の一般項を求める
  •  

    計算

    $\{b_n\}$ が満たす漸化式を求める

     
    詳細(click)

    $\{a_n\}$ に関する漸化式より

    $$
    \begin{eqnarray*}
    a_{n+4} & = & -2a_{n+3} + a_{n+2} + 2a_{n+1}-1\\
    a_{n+3} & = & -2a_{n+2} + a_{n+1} + 2a_n-1
    \end{eqnarray*}
    $$

    である.辺々引いて
    \[
    a_{n+4}-a_{n+3}=-2(a_{n+3}-a_{n+2}) + (a_{n+2}-a_{n+1}) + 2(a_{n+1}-a_n).
    \]
    ゆえに $b_{n} = a_{n+1}-a_{n}$ とすれば
    \[
    b_{n+3} =-2b_{n+2} + b_{n+1} + 2b_n
    \]
    が成り立つ.また
    \[
    b_1 = a_2-a_1 = 1, \quad b_2 = a_3-a_2 = 1, \quad b_3 = a_4-a_3 =-3-3 =-6
    \]
    より $\{b_n\}$ が満たす $3$ 項間の漸化式が得られた.この漸化式が定数項を持たないことがポイントである.

    //
     

    $3$ 次正方行列 $A$ を求める

     
    詳細(click)

    $$
    \begin{eqnarray*}
    \boldsymbol{x}_{n+1} = \left[
    \begin{array}{c}
    b_{n+3} \\
    b_{n+2} \\
    b_{n+1}
    \end{array}
    \right]
    & = &
    \left[
    \begin{array}{c}
    -2b_{n+2} + b_{n+1} + 2b_n \\
    b_{n+2} \\
    b_{n+1}
    \end{array}
    \right] \\
    & = &
    \left[
    \begin{array}{ccc}
    -2 & 1 & 2 \\
    1 & 0 & 0 \\
    0 & 1 & 0
    \end{array}
    \right]
    \left[
    \begin{array}{c}
    b_{n+2} \\
    b_{n+1} \\
    b_{n}
    \end{array}
    \right]
    =
    \left[
    \begin{array}{ccc}
    -2 & 1 & 2 \\
    1 & 0 & 0 \\
    0 & 1 & 0
    \end{array}
    \right]\boldsymbol{x}_n
    \end{eqnarray*}
    $$

    が成り立つ.したがって $3$ 次正方行列
    \[
    A = \left[
    \begin{array}{ccc}
    -2 & 1 & 2 \\
    1 & 0 & 0 \\
    0 & 1 & 0
    \end{array}
    \right]
    \]
    が $\boldsymbol{x}_{n+1} = A \boldsymbol{x}_n$ を満たす.

    //
     

    $A^n$ を求める

     
    詳細(click)

    \[
    \boldsymbol{x}_n = A\boldsymbol{x}_{n-1} = A^2\boldsymbol{x}_{n-2} = \cdots = A^{n-1}\boldsymbol{x}_1
    \]

    であるから,$A^{n}$ を求めれば $\boldsymbol{x}_n$ が判る.$A^{n}$ を求めるために $A$ を対角化する.すなわち $P^{-1}AP$ が対角行列となるような正則行列 $P$ を求める.

    $E$ を 3次の単位行列として
    \[
    |xE-A| = (x-1)(x+1)(x+2)
    \]
    であるから,行列 $A$ の固有値は $x = -2, -1, 1$ である(それぞれ重複度は1).
    $x=-2$ に対して
    \[
    xE-A = \left[
    \begin{array}{ccc}
    0 & -1 & -2 \\
    -1 & -2 & 0 \\
    0 & -1 & -2
    \end{array}
    \right]
    \xrightarrow{行基本変形} \left[
    \begin{array}{ccc}
    1 & 0 & -4 \\
    0 & 1 & 2 \\
    0 & 0 & 0
    \end{array}
    \right]
    \]
    であるから,固有ベクトルとして,例えば
    \[
    \boldsymbol{p}_1 = \left[
    \begin{array}{c}
    4 \\
    -2 \\
    1
    \end{array}
    \right]
    \]
    を得る.

    $x=-1$ に対して
    \[
    xE-A = \left[
    \begin{array}{ccc}
    1 & -1 & -2 \\
    -1 & -1 & 0 \\
    0 & -1 & -1
    \end{array}
    \right]
    \xrightarrow{行基本変形} \left[
    \begin{array}{ccc}
    1 & 0 & -1 \\
    0 & 1 & 1 \\
    0 & 0 & 0
    \end{array}
    \right]
    \]
    であるから,固有ベクトルとして,例えば
    \[
    \boldsymbol{p}_2 = \left[
    \begin{array}{c}
    1 \\
    -1 \\
    1
    \end{array}
    \right]
    \]
    を得る.

    $x=1$ に対して
    \[
    xE-A = \left[
    \begin{array}{ccc}
    3 & -1 & -2 \\
    -1 & 1 & 0 \\
    0 & -1 & 1
    \end{array}
    \right]
    \xrightarrow{行基本変形} \left[
    \begin{array}{ccc}
    1 & 0 & -1 \\
    0 & 1 & -1 \\
    0 & 0 & 0
    \end{array}
    \right]
    \]
    であるから,固有ベクトルとして,例えば
    \[
    \boldsymbol{p}_3 = \left[
    \begin{array}{c}
    1 \\
    1 \\
    1
    \end{array}
    \right]
    \]
    を得る.

    得られた3つの固有ベクトルを並べた行列
    \[
    \left[\boldsymbol{p}_1~~\boldsymbol{p}_2~~\boldsymbol{p}_3 \right]
    = \left[
    \begin{array}{ccc}
    4 & 1 & 1 \\
    -2 & -1 & 1 \\
    1 & 1 & 1
    \end{array}
    \right]
    \]
    が求める正則行列 $P$ である.$P^{-1}$ は掃き出し法(Gaussian elimination)により求める.
    \[
    \left[
    \begin{array}{ccc|ccc}
    4 & 1 & 1 & 1 & 0 & 0 \\
    -2 & -1 & 1 & 0 & 1 & 0 \\
    1 & 1 & 1 & 0 & 0 & 1
    \end{array}
    \right] \xrightarrow{行基本変形} \left[
    \begin{array}{ccc|ccc}
    1 & 0 & 0 & \frac{1}{3} & 0 & -\frac{1}{3} \\
    0 & 1 & 0 & -\frac{1}{2} & -\frac{1}{2} & 1 \\
    0 & 0 & 1 & \frac{1}{6} & \frac{1}{2} & \frac{1}{3}
    \end{array}
    \right]
    \]
    より
    \[
    P^{-1}= \left[
    \begin{array}{ccc}
    \frac{1}{3} & 0 & -\frac{1}{3} \\
    -\frac{1}{2} & -\frac{1}{2} & 1 \\
    \frac{1}{6} & \frac{1}{2} & \frac{1}{3}
    \end{array}
    \right]
    = \frac{1}{6}\left[
    \begin{array}{ccc}
    -2 & 0 & 2 \\
    -3 & -3 & 6 \\
    1 & 3 & 2
    \end{array}
    \right]
    \]
    を得る.この正則行列 $P$ によって行列 $A$ は対角化される:
    \[
    P^{-1}AP = \left[
    \begin{array}{ccc}
    -2 & 0 & 0 \\
    0 & -1 & 0 \\
    0 & 0 & 1
    \end{array}
    \right].
    \]
    いま
    $$
    \begin{eqnarray*}
    \left[
    \begin{array}{ccc}
    (-2)^n & 0 & 0 \\
    0 & (-1)^n & 0 \\
    0 & 0 & 1
    \end{array}
    \right] & = & (P^{-1}AP)^n \\
    & = & (P^{-1}AP)(P^{-1}AP)\cdots(P^{-1}AP) = P^{-1}A^nP
    \end{eqnarray*}
    $$
    であるから
    $$
    \begin{eqnarray*}
    A^n & = & P\left[
    \begin{array}{ccc}
    (-2)^n & 0 & 0 \\
    0 & (-1)^n & 0 \\
    0 & 0 & 1
    \end{array}
    \right]P^{-1} \\
    & = & \frac{1}{6}\left[
    \begin{array}{ccc}
    2(-2)^{n+2}-3(-1)^{n+2}+1 & -3(-1)^{n+2}+3 & -2(-2)^{n+2}+6(-1)^{n+2}+2 \\
    2(-2)^{n+1}-3(-1)^{n+1}+1 & -3(-1)^{n+1}+3 & -2(-2)^{n+1}+6(-1)^{n+1}+2 \\
    2(-2)^{n}-3(-1)^{n}+1 & -3(-1)^{n}+3 & -2(-2)^{n}+6(-1)^{n}+2
    \end{array}
    \right]
    \end{eqnarray*}
    $$
    を得る.実際は移項の計算に用いるのはいずれか $1$ 行だけであり,残る $2$ 行は計算しなくてもよい.

    //
     

    $\{b_n\}$ の一般項を求める

     
    詳細(click)

    $$
    \begin{eqnarray*}
    A^{n-1}\boldsymbol{x}_1 & = & \frac{1}{6}\left[
    \begin{array}{ccc}
    (-2)^{n-1} & 0 & 0 \\
    0 & (-1)^{n-1} & 0 \\
    0 & 0 & 1
    \end{array}
    \right]\left[
    \begin{array}{c}
    -6 \\
    1 \\
    1
    \end{array}
    \right] \\
    & = &
    \frac{1}{6}\left[
    \begin{array}{c}
    -14(-2)^{n+1} + 21(-1)^{n+1}-1 \\
    -14(-2)^{n} + 21(-1)^{n}-1 \\
    -14(-2)^{n-1} + 21(-1)^{n-1}-1
    \end{array}
    \right]
    \end{eqnarray*}
    $$
    であるから,$\boldsymbol{x}_n = A^{n-1}\boldsymbol{x}_1$ の両辺の第 $3$ 成分を比較して
    \[
    b_n = \frac{-14(-2)^{n-1} + 21(-1)^{n-1}-1}{6}
    \]
    が得られた.

    //
     

    $\{a_n\}$ の一般項を求める

     
    詳細(click)

    \[
    a_{n+1}-a_n = b_n = \frac{-14(-2)^{n-1} + 21(-1)^{n-1}-1}{6}
    \]
    であるから,階差数列の考え方を用いて $n \geqq 2$ のとき
    $$
    \begin{eqnarray*}
    a_n & = & a_1 + \sum_{k=1}^{n-1}\frac{1}{6}\biggl\{-14(-2)^{k-1} + 21(-1)^{k-1}-1\biggr\} \\
    & = & 1-\frac{7}{9}\biggl\{1-(-2)^{n-1}\biggr\} + \frac{7}{4}\biggl\{1-(-1)^{n-1}\biggr\}-\frac{1}{6}n+\frac{7}{6} \\
    & = & \frac{77-14(-2)^n +63(-1)^n-6n}{36}
    \end{eqnarray*}
    $$
    を得る.これは $n=1$ でも成り立つ.

    //
     

    補足:定数項を含んだまま解く場合

    定数項を含んだまま解く場合は
    \[
    \boldsymbol{x}_{n} = \left[
    \begin{array}{c}
    b_{n+2} \\
    b_{n+1} \\
    b_{n}
    1
    \end{array}
    \right]
    \]
    とおいて,$\boldsymbol{x}_{n+1} = A \boldsymbol{x}_n$ を満たす $4$ 次正方行列 $A$ に関して計算すればよい.

     

    補足:特性方程式と行列の固有値

    上の例での計算結果から,漸化式に定数項を含まない
    \[
    a_{n+\ell} = p_1a_{n} + p_2a_{n+1} + p_3a_{n+2} + \cdots + p_{\ell}a_{n+\ell-1} \qquad (p_1 , p_1 , \dots , p_\ell \\in \mathbb{R})
    \]
    の形の$\ell + 1$項間漸化式から得られる数列 $\{a_n\}$ の一般項は,$\ell \times \ell$ 行列 $A$ の固有値 $\alpha_1 , \alpha_2, \ldots \alpha_\ell$ に対して
    \[
    a_n = c_1\alpha_{1}^{n-1} + c_2\alpha_{2}^{n-1} + \cdots + c_\ell\alpha_\ell^{n-1} \quad (c_1,c_2,\ldots,c_\ell \in \mathbb{R})
    \]
    の形で与えられると推測される.実際,結果は固有値が重複しない場合には正しい.

    またその固有値は方程式
    \[
    -x^{\ell} = p_1 + p_2x + p_3x^2 + \cdots + p_{n+\ell}x^{\ell-1}
    \]
    の解と一致する.例えばよく知られた例として,$3$ 項間の漸化式
    \[
    a_{n+2} = pa_{n+1} + qa_n
    \]
    に対して
    \[
    \boldsymbol{x}_{n} = \left[
    \begin{array}{c}
    a_{n+1} \\
    a_{n}
    \end{array}
    \right]
    \]
    とすると
    \[
    \boldsymbol{x}_{n+1} = \left[
    \begin{array}{c}
    a_{n+2} \\
    a_{n+1}
    \end{array}
    \right]
    =
    \left[
    \begin{array}{c}
    pa_{n+1} + qa_n \\
    a_{n+1}
    \end{array}
    \right]
    =
    \left[
    \begin{array}{cc}
    p & q \\
    1 & 0
    \end{array}
    \right]
    \left[
    \begin{array}{c}
    a_{n+1} \\
    a_{n}
    \end{array}
    \right]
    =
    A\boldsymbol{x}_n
    \]
    とできて
    \[
    |xE-A| = x^2 + px + q
    \]
    を得ることができる.これがいわゆる「特性方程式」である.

    固有値が重複する場合は行列が対角化できない可能性がある.そのときは対角化の代わりに例えば Jordan 標準形を用いて $A^n$ を求めればよい.

    Question 2

    漸化式
    \[
    a_{n+3} = a_{n+2} + a_{n+1}-a_n, \quad a_1 = 0, \quad a_2 = -1, \quad a_3 = 1
    \]
    で定められる数列 $\{a_n\} \quad (n=1,2,3,\ldots)$ の一般項を求めよ.

     

    解答は時間があれば後日こっそり載せておく.

    (2018/05/11 追記)n項間の漸化式#3 に解答の載せた.

    20180511 追記
    20190519 更新


    スポンサーリンク