Web Analytics Made Easy - StatCounter

工業大学生ももやまのうさぎ塾

4年間＋2年間の工業大学・大学院で学んだ知識やためになることを投稿していきます

トップ > 数学 > うさぎでもわかる離散数学　番外編2　差分方程式（漸化式）　前編

うさぎでもわかる離散数学　番外編2　差分方程式（漸化式）　前編

数学 数学-大学数学 数学-大学数学-離散数学 まとめシリーズ

こんにちは！　ももやまです！
漸化式、差分方程式は数Bで少し習ったと思います。
今回は、漸化式の解き方と微分方程式っぽく解く別の解き方を紹介したいと思います。

１．差分方程式（漸化式）とは

皆さんは高校時代に数学Bで漸化式を習いましたよね。*1
差分方程式（漸化式）とは、ある答えを、少し前の答えとはじめの答えを使って出すような式のことです。例えば、 a_{n} = 3 a_{n-1} - 2 という式があるとします。これは、1つ前の答えを3倍したものに2を引いた値が答えになることを表します。

例えば、はじめの答え（初項）を a_0 = 5 とすると、1つ先の答え a_1 は 3 a_0 - 2 = 13 で出すことができます。 

★注意★
この記事では、初項を a_1 ではなく a_0 としてるので気をつけてください。初項が a_1 だと特殊解は a^{n-1} のような形で出ますが、 a_0 の場合は a^n の形で出てきます。
人によっては a_n という形ではなく、 f(n) を使って表す人もいるので気をつけてください。

例： a_{n} = 2 a_{n-1} + 1 は f(n) = 2f(n-1) + 1 と同じ

 

２．隣接３項間差分方程式

まずはつぎの漸化式を解いてみましょう。

\[ a_0 = 2, \  a_1 = 7, \  a_{n} - 3a_{n-1} + 2 a_{n-2} = 0 \]

の初期値による特殊解を求めなさい。

(1) 普通に解いてみる

とりあえず、高校のやり方とほぼ同じやり方で解いてみましょう。 
まずは特性方程式を解いてみましょう。
x^2-3x+2=0 より x = 1,2 となる。

よって、

\[\left\{ \begin{array}{l} a_n - a_{n-1} = 2(a_{n-1} - a_{n-2}) \\a_n - 2a_{n-1} = (a_{n-1} -2 a_{n-2}) \end{array}\right.\]

となる。この漸化式は、

a_{n+1} - a_{n} = 2(a_{n} - a_{n-1}) = 2^2(a_{n-1} - a_{n-2}) =\cdots= 2^n(a_{1} - a_{0})= 5 \cdot 2^n
a_{n+1} - 2a_{n} = 1(a_{n} - 2a_{n-1}) = 1^2(a_{n-1} - 2a_{n-2}) =\cdots= 1^n(a_{1} - 2a_{0}) = 3

と変形できる。よって、

\left\{ \begin{array}{l} a_{n+1} - \ \ a_{n} = 5 \cdot 2^n \ \ \cdots (1) \\a_{n+1} - 2a_{n} = 3 \ \ \ \ \ \ \ \ \   \cdots (2) \end{array}\right.

となり、a_{n} = 5 \cdot 2^n - 3 \ \ [(1)-(2)] と求めることができる。

(2) 微分方程式っぽく解く

特性方程式まで求めるところは (1) と同じですが、特性方程式を求めたら解の形を予想してしまいます。特性方程式の解は x = 1,2 でしたよね。解の形を  A,B は任意の定数として、

\[ a_n = A \cdot 1^n + 2^n \cdot B = A + 2^n B \]

とおく。これを一般解といいます。

すると、 A + 2^0 B = A + B = a_0 = 2,   A + 2^1 B = A + 2B = a_1 = 7 の2つの式が成立する。すると、

\[\left\{ \begin{array}{l} A + \ \ B = 2 \ \ \cdots (1) \\ A + 2B = 7 \ \   \cdots (2) \end{array}\right.\]

見た瞬間2つの解はわかるけど、今回はあえて逆行列使って解いてみます。
もちろん行列を使わなくても計算は可能です。

逆行列を使って連立方程式を解く方法についてはこちらでまとめているので、わからない人は参考までにどうぞ。

momoyama1192.hatenablog.com

\[\left( \begin{array}{ccc} 1 & 1  \\ 1 & 2  \end{array} \right) \left( \begin{array}{ccc} A  \\ B  \end{array} \right) =\left( \begin{array}{ccc} 2  \\ 7  \end{array} \right)\]

という行列を満たせばいい。ここで逆行列を求める。

\[\left( \begin{array}{ccc} 1 & 1  \\ 1 & 2  \end{array} \right)^{-1} =\left( \begin{array}{ccc} 2 & -1  \\ -1 & 1  \end{array} \right)\]

なので、

\[\left( \begin{array}{ccc} A  \\ B  \end{array} \right) =  \left( \begin{array}{ccc} 1 & 1  \\ 1 & 2  \end{array} \right)^{-1} \left( \begin{array}{ccc} 2  \\ 7  \end{array} \right)\ =   \left( \begin{array}{ccc} 2 & -1  \\ -1 & 1  \end{array} \right) \left( \begin{array}{ccc} 2  \\ 7  \end{array} \right)\ = \left( \begin{array}{ccc} 3  \\ 5  \end{array} \right)\ \]

となる。（ A A^{-1} = A^{-1} A = E より、元の行列とその行列の逆行列（順番はどっちでもOK）は必ず単位行列）

なので、 A = -3, B = 5 となり、特殊解は a_{n} = 5 \cdot 2^n - 3 となる。

３．隣接３項間差分方程式（重解あり）

重解があるパターンもやってみよう。\[ a_0 = 2, \  a_1 = 10, \  a_{n} - 4a_{n-1} + 4 a_{n-2} = 0\]

(1) 普通に解いてみる

x^2-4x+4=0 より x = 2 となる。

あれ、重解になる！　式が１つしかでない！

慌てないでください。まずは１つ式をたてて変形しちゃいましょう。

\[\begin{eqnarray}a_{n+1} - 2a_{n} = 2(a_{n} - 2a_{n-1}) = 2^2(a_{n-1} - 2a_{n-2}) = \cdots = 2^n (a_1 - 2 a_0) = 6 \cdot 2^n \end{eqnarray}\]

 となりますよね。つぎに両辺を 2^{n+1} で割ります。

\[ \frac{a_{n+1}}{2^{n+1}} - \frac{a_{n}}{2^{n}} = 3 \]

さらに \frac{a_{n}}{2^n} = b_{n} とします。すると、
\[ b_{n} - b_{n-1} = 3 \] となります。\frac{a_{0}}{2^0} = b_{0} = 2 より、
\[b_{n} = 2 + n \times 3 = 3n + 2\]
となる。よって、\frac{a_{n}}{2^n} = b_{n} より、

\[ a_n = 2^n \times b_{n} = 2^n(3n + 2)\]

と計算でき、特殊解は  2^n(3n + 2) となる。
意外とめんどいでしょ！　ということで(2)の少し楽なやり方でやってみます。

(2) 微分方程式っぽく解く

特性方程式が重解であった場合の予想する式は変わってきます。今回の場合は、特性方程式の解は2だったので、 A,B は任意の定数として

\[a_n = 2^n (An + B)\]

と予想します。（一般解）（この形は基本変わらない）

すると、 B = a_0 = 2,   2A + 2B = a_1 = 10 の2つの式が成立する。

\[\left\{ \begin{array}{l} \ \ \ \ \ \ \ \ \ \ \ B =  \ \ 2 \ \ \cdots (1) \\ 2A + 2B = 10 \ \   \cdots (2) \end{array}\right.\]

さすがにこの式は行列使って計算するまでもないので普通に計算する。すると、 A = 3, B= 2 となる。よって特殊解は、

\[a_n = 2^n (3n + 2)\]

となる。

４．隣接４項間差分方程式

４項間の差分方程式も微分方程式チックに解くことができちゃいます。４項間以上の場合は微分方程式チックに解いたほうが早く特殊解まで出すことができます。

実は隣接４項間は横浜国立大学の入試で出題されています。（もちろん誘導あり）

数列\{a_n\}がa_{n+3}=10a_{n+2}-31a_{n+1}+30a_n~(n=0,~1,~2,~\cdots)をみたしているとき，

(1) 3次方程式x^3=10x^2-31x+30は異なる3実数解\alpha,~\beta,~\gamma~(\alpha<\beta<\gamma)をもつ．\alpha,~\beta,~\gammaの値を求めよ．
(2) \alpha,~\betaを(1)で求めたものとする．b_n=a_{n+1}-\alpha a_n~(n=0,~1,~2,~\cdots)とおくとき，b_{n+2}をb_{n+1},~b_nの式で表せ．
さらにc_n=b_{n+1}-\beta b_{n}~(n=0,~1,~2,~\cdots)とおくとき，c_{n+1}をc_nの式で表せ．
(3) a_0=1,~a_1=2,~a_2=5のとき，c_n,~b_n,~a_nをそれぞれnの式で表せ

引用：大学入試から学ぶ高校数学　横浜国立大学

微分方程式チックではない解答はリンク先に用意されてあったのでそちらを参考にしてください。

ではこれを微分方程式っぽく解いてみます。

\[a_{n} - 10a_{n-1} + 31a_{n-2} - 30a_{n-3} =0, \ a_0 = 1, \ a_1 = 2, \ a_2 = 5 \]

の一般解を出します。まずは特性方程式から、(1)の誘導に相当します。

\[x^3 - 10x^2 + 31x - 30 = (x-2)(x^2-8x+15) \\=(x-2)(x-3)(x-5)=0 \]

より x=2,3,5 となる。解の形を  A,B,C は任意の定数として、

\[a_n = 2^n \cdot A + 3^n \cdot B + 5^n \cdot C \]

とおく。これが一般解となる。あとは3つの初期値を使って A,B,C の3変数の方程式を作るだけ。

(i) n = 0 のとき、 A + B + C = a_0 = 1 となる。
(ii) n = 1 のとき、 2A + 3B + 5C = a_1 = 2 となる。
(iii) n = 2 のとき、 4A + 9B + 25C = a_2 = 5 となる。

さて今回も逆行列を使って連立方程式をときます。

\[\left( \begin{array}{ccc} 1 & 1 & 1  \\ 2 & 3 & 5 \\ 4 & 9 & 25  \end{array} \right) \left( \begin{array}{ccc} A  \\ B \\ C  \end{array} \right) =\left( \begin{array}{ccc} 1  \\ 2 \\ 5  \end{array} \right)\]

となる。逆行列は、

\[\left( \begin{array}{ccc} 1 & 1 & 1  \\ 2 & 3 & 5 \\ 4 & 9 & 25  \end{array} \right)^{-1} =\frac{1}{6} \left( \begin{array}{ccc} 30 & -16 & 2  \\ -30 & 21 & -3 \\ 6 & -5 & 1  \end{array} \right)\]

となる。よって、

\[\left( \begin{array}{ccc} A  \\ B \\ C  \end{array} \right) =  \left( \begin{array}{ccc}1 & 1 & 1  \\ 2 & 3 & 5 \\ 4 & 9 & 25  \end{array} \right)^{-1} \left( \begin{array}{ccc} 1  \\ 2 \\ 5  \end{array} \right)\ = \frac{1}{6}  \left( \begin{array}{ccc} 30 & -16 & 2  \\ -30 & 21 & -3 \\ 6 & -5 & 1  \end{array} \right) \left( \begin{array}{ccc} 1 \\ 2  \\ 5  \end{array} \right)\ = \frac{1}{6} \left( \begin{array}{ccc} 8  \\ -3 \\ 1  \end{array} \right)\ \]

となり、 A = \frac{4}{3}, B = - \frac{1}{2}, C = \frac{1}{6} と求められる。

よって、特殊解は、

\[a_n =\frac{4}{3} \cdot 2^n  - \frac{1}{2} \cdot 3^n +  \frac{1}{6} \cdot 5^n =\frac{1}{6}(2^{n+3} - 3^{n+1} + 5^n)\]

と求められる。

５．隣接４項間差分方程式（重解あり）

特性方程式が重解がある場合、予想する式は変化します。
例えば次の問題を解いてみましょう。

\[a_{n} - 5a_{n-1} + 3a_{n-2} + 9a_{n-3} =0 \ a_0 = 0, \ a_1 = -6, \ a_2 = 12 \]

いつものようにまずは特性方程式をときます。

x^3 - 5x^2 + 3x - 9 = (x+1)(x^2-6x+9) \\=(x+1)(x-3)^2=0

よって 1 と 3（2重解）となる。
ここで3が2重解になりましたよね。なので3の部分だけ An + B とします。よって一般解は、 A,B,C は任意の定数として、

\[a_n = (An+B) \cdot 3^n + C \cdot (-1)^n \]

となる。あとは場合分け。

(i) n = 0 のとき、 B + C = a_0 = 0
(ii) n = 1 のとき、 3A + 3B - C = a_1 = -6
(iii) n = 2 のとき、 18A + 9B + C = a_2 = 12

今回も逆行列使っちゃいましょう。

\[\left( \begin{array}{ccc} 0 & 1 & 1  \\ 3 & 3 & -1 \\ 18 & 9 & 1  \end{array} \right) \left( \begin{array}{ccc} A  \\ B \\ C  \end{array} \right) =\left( \begin{array}{ccc} 0  \\ -6 \\ 12  \end{array} \right)\]

となる。逆行列は、

\[\left( \begin{array}{ccc} 0 & 1 & 1  \\ 3 & 3 & -1 \\ 18 & 9 & 1  \end{array} \right)^{-1} =\frac{1}{48} \left( \begin{array}{ccc} -12 & -8 & 4  \\ 21 & 18 & -3 \\ 27 & -18 & 3  \end{array} \right)\]

となる。よって、

\[\left( \begin{array}{ccc} A  \\ B \\ C  \end{array} \right) =  \left( \begin{array}{ccc}0 & 1 & 1  \\ 3 & 3 & -1 \\ 18 & 9 & 1  \end{array} \right)^{-1} \left( \begin{array}{ccc} 0  \\ -6 \\ 12  \end{array} \right)\ = \frac{1}{48}  \left( \begin{array}{ccc}-12 & -8 & 4  \\ 21 & 18 & -3 \\ 27 & -18 & 3  \end{array} \right) \left( \begin{array}{ccc} 0\\ -6  \\ 12  \end{array} \right)\ = \left( \begin{array}{ccc} 2  \\ -3 \\ 3  \end{array} \right)\ \]

となり、 A = 2, B = -3, C = 3 と求められる。
よって特殊解は、

\[a_n = (2n-3) \cdot 3^n + 3 \cdot (-1)^n \]

となる。

６．連立差分方程式

連立漸化式を解いたことありますか？
連立漸化式も隣接３項間の差分方程式に書き換えちゃうことができます。

１問解いてみましょう。 a_0 = 7, \ b_0 = -4 とします。

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

まずはこの連立差分方程式を隣接３項間差分方程式に変えます。

\[b_{n-1} = a_n - 2a_{n-1} \\ b_{n} = a_{n+1} - 2a_{n} \] 

なので、これを代入する。

\[a_{n+1} - 2a_{n} = 2a_{n-1} + 3(a_n - 2a_{n-1}) \]
\[a_{n+1} - 5a_{n} + 4a_{n-1} = 0\]
\[a_{n} - 5a_{n-1} + 4a_{n-2} = 0\]

となる。あとはいつも通り特性方程式を解くだけ。
\[ x^2 - 5x + 4 = (x-1)(x-4)=0\]

より、解は1と4（重解なし）。よって一般解は、

\[ a_n = A \cdot 4^n + B\]

となる。ここで、 a_1 = 2a_0 + b_0 = 10 となる。

(i) n = 0 のとき、 A + B = a_0 = 7
(ii) n = 1 のとき、 4A + B = a_1 = 10 となる。

よって、 A = 1, B = 6 となる。よって特殊解は、

\[ a_n = 1 \cdot 4^n + 6 = 4^n + 6\]

となる。また、 b_{n} = a_{n+1} - 2a_{n} なので、

b_{n} = 4^{n+1} + 6 - 2(4^n + 6) = 4 \cdot 4^n + 6 - 2 \cdot 4^n - 12 \\ = 2 \cdot 4^n - 6

と求められる。

 

公式まとめ

初項が a_0 のとき、

(1) 隣接３項間差分方程式の一般解
※ A,B は任意の定数

[重解なしのとき　解を \alpha, \beta とする]
\[a_n = A \cdot \alpha^n + B \cdot \beta^n \]
[解 \alpha が重解のとき]
\[a_n = (An + B) \cdot \alpha^n \]

(2) 隣接４項間差分方程式の一般解
※ A,B,C は任意の定数

[重解なしのとき　解を \alpha, \beta, \gamma とする]
\[a_n = A \cdot \alpha^n + B \cdot \beta^n + C \cdot \gamma^n \]
[ \alpha が2重解のとき　解を \alpha, \beta とする]
\[a_n = (An+B) \cdot \alpha^n + C \cdot \beta^n\]
[ \alpha が3重解のとき]
\[a_n = (An^2+Bn+C) \cdot \alpha^n \]

予想したあとは初項を入れて A,B,C などの定数を連立方程式などで解いてやればよい。

 

注意
(1) 解とは特性方程式の解のことである。
(2) 初項が a_0 ではなく a_1 の場合、n乗をn-1乗に置き換えること。

 

 

７．練習

では１問練習してみましょう。

問題

a_{n} - 6 a_{n-1} + 12 a_{n-2} - 8 a_{n-3} = 0 について、

(1) 定数 A,B,C を用いて一般解を求めなさい。
(2) a_0 = 1, a_1 = 6, a_2 = 4 のときの特殊解を求めなさい。

解答

(1) まずは特性方程式をときましょう。

\[x^3-6x^2+12x-8 = (x-2)(x^2-4x+4) = (x-2)^3 \]

となり、なんと2の3重解となる。よって一般解は

\[a_n = (An^2+Bn+C) \cdot 2^n\]

となる。ただし A,B,C は任意の定数である。

(2)

n = 0 のとき、 C = a_0 = 1
n = 1 のとき、 2A+ 2B + 2C = a_1 = 6
n = 2 のとき、 16A + 8B + 4C = a_2 = 4

の3つの方程式が成り立つ。今回も逆行列でやっちゃうよ。

\[\left( \begin{array}{ccc} 0 & 0 & 1  \\ 2 & 2 & 2 \\ 16 & 8 & 4 \end{array} \right) \left( \begin{array}{ccc} A  \\ B \\ C  \end{array} \right) =\left( \begin{array}{ccc} 1  \\ 6 \\ 4  \end{array} \right)\]

となる。逆行列は、

\[\left( \begin{array}{ccc} 0 & 0 & 1  \\ 2 & 2 & 2 \\ 16 & 8 & 4   \end{array} \right)^{-1} =\frac{1}{8} \left( \begin{array}{ccc} 4 & -4 & 1  \\ -12 & 8 & -1 \\ 8 & 0 & 0  \end{array} \right)\]

となる。よって、

\[\left( \begin{array}{ccc} A  \\ B \\ C  \end{array} \right) =  \left( \begin{array}{ccc}0 & 0 & 1  \\ 2 & 2 & 2 \\ 16 & 8 & 4  \end{array} \right)^{-1} \left( \begin{array}{ccc} 1 \\ 6 \\ 4  \end{array} \right)\ = \frac{1}{8}  \left( \begin{array}{ccc} 4 & -4 & 1  \\ -12 & 8 & -1 \\ 8 & 0 & 0  \end{array} \right) \left( \begin{array}{ccc}  1\\ 6  \\ 4  \end{array} \right)\ = \left( \begin{array}{ccc} -2  \\ 4 \\ 1  \end{array} \right)\ \]

となり、 A = -2, B = 4, C = 1 と求められる。よって特殊解は、

\[ a_n = (-2n^2 + 4n + 1) \cdot 2^n \]

と求められる。

８．さいごに

今回は、隣接３、４項間差分方程式の解き方、連立差分方程式の解き方をまとめてみました。このように項を予測するやり方でやれば、隣接５項だろうが６項だろうが解くことができるようになります（めんどくさいけど）。

この記事から差分方程式、もしくは漸化式の解き方がわかるようになればありがたいです。

今回は（右辺）= 0の差分方程式でしたが、次の記事では（右辺）= 0ではない場合の差分方程式の解き方も説明したいと思います。

それではまた次回。ばいばーい！

差分方程式後編はこちら！

www.momoyama-usagi.com

*1:習ったと信じたい