次: 三項間漸化式を解く 上: 三項間漸化式と行列の累乗

三項間漸化式と連立漸化式

拓生　定期テストで，三項間漸化式

$$a_{n+2}=2a_{n+1}+3a_n\,,\quad a_0=1,\,\, a_1=1$$

を解く問題が出ました． 特性方程式 $t^2-2t-3=0$の二つの解が $3$ と $-1$で異なります． 特性方程式の異なる二つの解が $\alpha,\ \beta$のとき $a_n$がいつも $\alpha^{n-1},\ \beta^{n-1}$ からできているので，求める数列を

$$a_n=p\cdot3^n+q\cdot(-1)^n$$

と置いて，最初の二項が一致するように $p$ と $q$ を求めました． でも試験では大幅に減点でした．

南海　数列がいつもこの形をしていることに気づいたのはよい． しかしただ単に計算だけするのは解答としては不十分だ． このように書けることはどんな意味があるのか考え， なぜこの形になるのか論証しなければならない．

拓生　もう一つ質問ですが，連立漸化式

$$\left\{ \begin{array}{l} a_{n+1}=2a_n+3b_n\\ b_{n+1}=a_n+2b_n \end{array}\right.$$

を解こうとしていろいろやっていると，

$$a_{n+2}-4a_{n+1}+a_n=0$$

が得られました．その変形はいつもできそうですが， 連立漸化式と三項間漸化式の関係がはっきりしていません．

南海　なるほど．それならこの機会に 三項間漸化式と連立漸化式についてまとめておこう． まず三項間漸化式と連立二項間漸化式の相互関係だ．

三項間漸化式と連立二項間漸化式の定義

数列 $\{a_n\}$ と $n$ の関数 $f(n)$ があってその間に

$$a_{n+2}=pa_{n+1}+qa_n+f(n)$$

の関係式がすべての $n$ に対して成り立つとき，この関係式を三項間漸化式という． $(a_1,\ a_0)$ の値が決まれば，数学的帰納法によって数列 $\{a_n\}$の各項の値が一意に定まる． $f(n)=g(n+2)-pg(n+1)-qg(n)$となる0以上の整数を定義域とする関数$g(n)$が見つかれば，これは

$$\{a_{n+2}-g(n+2)\}=p\{a_{n+1}-g(n+1)\}+q\{a_n-g(n)\}$$

となる．$f(n)=0$ の場合に解けることが，基本だ． それで以下では

$$a_{n+2}=pa_{n+1}+qa_n\quad\cdots\maru{1}$$

となる漸化式を考えよう．

次に，二つの数列 $\{x_n\}$ と$\{y_n\}$ の間に成り立つ

$$\left\{\begin{array}{l} x_{n+1}=a x_n+by_n\\ y_{n+1}=c x_n+dy_n \end{array}\right.\quad\cdots\maru{2}$$

のような漸化式を連立二項間漸化式という． $$\vecarray{x_0}{y_0}$$ の値が定まれば， 二つの数列 $\{x_n \},\ \{y_n \}$ の各項の値が一意に定まる．

この二つの形の漸化式は，実は同等である．つまり一方から他方への変換があり， それによって，一方が解ければ他方が解ける．

連立二項間漸化式から三項間漸化式へ

まず，連立二項間漸化式2を考えよう． 行列$A$を $A=\matrix{a}{b}{c}{d}$とすると2は

$$\vecarray{x_{n+1}}{y_{n+1}}=A\vecarray{x_n}{y_n}$$

と表される．したがって，等比数列と同様に

$$\vecarray{x_n}{y_n}=A^n\vecarray{x_0}{y_0}$$

となる． ハミルトン・ケイレイの定理より

$$A^2-(a+d)A+(ad-bc)E=0$$

つまり

$$A^{n+2}-(a+d)A^{n+1}+(ad-bc)A^n=0\quad\cdots\maru{3}$$

である．これからまた

$$\begin{eqnarray*} &&A^{n+2}\vecarray{x_0}{y_0}-(a+d)A^{n+1}\vecarray{x_0}{y_0}+(... ...ay{x_{n+1}}{y_{n+1}}+(ad-bc)\vecarray{x_n}{y_n} =\vecarray{0}{0} \end{eqnarray*}$$

つまり, 数列 $\{x_n\}$ と$\{y_n\}$ はともに同じ三項間漸化式をみたす.

$$\left\{\begin{array}{l} x_{n+2}=(a+d)x_{n+1}-(ad-bc)x_n\\ y... ...=(a+d)y_{n+1}-(ad-bc)y_n \end{array}\right.\quad\cdots\maru{4}$$

をみたす.

このとき，それぞれの三項間漸化式の初期条件は

$$(x_1,\ x_0)=(ax_0+by_0,\ x_0),\ (y_1,\ y_0)=(cx_0+dy_0,\ y_0)$$

である．

三項間漸化式から連立二項間漸化式へ

こんどは三項間漸化式1を考えよう． $q= 0$ なら実質は二項間等比数列なので $q\ne 0$ とする． $p=a+d,\ q=-(ad-bc)$ となるような数 $a,\ b,\ c,\ d$ を一組とる． 同じ理由で $b\ne 0$ にとる． その組に対して

$$\left\{\begin{array}{l} a_{n+1}=a a_n+b b_n\\ b_{n+1}=c a_n+d b_n \end{array}\right.$$

とおく． 初期条件は $$\vecarray{a_0}{b_0}=\vecarray{a_0}{\dfrac{a_1-aa_0}{b}}$$ とする． これは $a_1=a a_0+b b_0$ であるように $b_0$ をとるということである． 行列 $A=\matrix{a}{b}{c}{d}$ とおくと

$$A^2-(a+d)A+(ad-bc)E=A^2-pA-qE=0$$

となる． ゆえに，この連立二項間漸化式から三項間漸化式を作る方法で作り直した数列 $\{a_n\}$ はもとの三項間漸化式1の解になる． なお数列 $\{b_n\}$ の方は $a,\ b,\ c,\ d$ の取り方で異なる． 実際に解くときは $a=p,\ b=q,\ c=1,\ d=0$ という組を用いればよい．つまり

$$\left\{\begin{array}{l} a_{n+1}=p a_n+qb_n\\ b_{n+1}=a_n \end{array}\right.\quad\cdots\maru{5}$$

とおく．初期条件は $$\vecarray{a_0}{b_0}=\vecarray{a_0}{\dfrac{a_1-pa_0}{q}}$$ である．

以上から，三項間漸化式を解くことと連立二項間漸化式を解くことは同等である．

次: 三項間漸化式を解く 上: 三項間漸化式と行列の累乗