2014/05/03

三項間漸化式の3通りの解き方

分野: 数列  レベル: 最難関大学

三項間漸化式:
$a_{n+2}=pa_{n+1}+qa_n$
の3通りの解法と,それぞれのメリットデメリットを解説します。

1:特性方程式を用いた解法
2:答えを気合いで予想する
3:行列の $n$ 乗を求める方法

例題として,$a_1=1,a_2=1,a_{n+2}=5a_{n+1}-6a_n$ を解きます。
特性方程式の解が重解になる場合は最後に補足します。

1:特性方程式を用いた解法

教科書に乗っている定番の解法です。

特性方程式 $x^2-5x+6=0$ の解は $x=2,3$ であり,漸化式は以下のように変形できる:
$a_{n+2}-2a_{n+1}=3(a_{n+1}-2a_{n})$
$a_{n+2}-3a_{n+1}=2(a_{n+1}-3a_{n})$
よって,上の式から $a_{n+1}-2a_n$ は公比 $3$ の等比数列となる:
$a_{n+1}-2a_n=3^{n-1}(a_2-2a_1)=-3^{n-1}$
同様に下の式から $a_{n+1}-3a_n$ は公比 $2$ の等比数列となる:
$a_{n+1}-3a_n=2^{n-1}(a_2-3a_1)=-2^n$
以上2つの式から $a_{n+1}$ を消去する:
$a_n=2^n-3^{n-1}$

メリット:定番の方法だから安心感がある
デメリット:記述量が少し多い

2:答えを気合いで予想する

三項間漸化式の特性方程式の解を $\alpha,\beta$ とおくと,漸化式の一般項は
$a_{n}=A\alpha^n+B\beta^n$
と表される。 $A,B$ は初期条件から求める。

特性方程式 $x^2-5x+6=0$ の解は $x=2,3$ である。…(1)
一般項を以下の形と予想する。
$a_{n}=2^nA+3^nB$
実際に漸化式に代入すると成立していることが分かる。…(2)
ここで,$n=1,2$ を代入すると,
$1=2A+3B,1=4A+9B$
これを解いて $A=1,B=-\dfrac{1}{3}$
よって,$a_{n}=2^n-3^{n-1}$

記述式の場合(1)の文言は不要ですが,(2)は必須です。
メリット:記述量が少ない,一般の $n$ 項間漸化式に拡張できる,漸化式の構造が微分方程式の構造に似ていることが分かる
デメリット:邪道なので解法1を覚えた上で使うべし

ちなみに四項間漸化式 $a_{n+3}=pa_{n+2}+qa_{n+1}+ra_{n}$ の場合は,$x^3=px^2+qx+r$ の解を $\alpha,\beta,\gamma$ とすると一般項は $a_n=A\alpha^n+B\beta^n+C\gamma^n$
と書けます。 $n$ 項間漸化式でも同様です!→漸化式の特性方程式の意味とうまくいく理由

行列の $n$ 乗を用いる方法

新課程で行列は扱わなくなってしまいましたが,漸化式の一般的な議論をする際には重要な考え方です。(具体的に漸化式の一般項を求めるのには不向きです)

与えられた漸化式は行列を用いて以下のように変形できる:
$\begin{pmatrix}
a_{n+2}\\a_{n+1}
\end{pmatrix}
=\begin{pmatrix}
5&-6\\
1&0\end{pmatrix}
\begin{pmatrix}
a_{n+1}\\a_{n}\end{pmatrix}$
よって,この式を繰り返し用いると,
$\begin{pmatrix}
a_{n+1}\\a_{n}
\end{pmatrix}
=\begin{pmatrix}
5&-6\\
1&0\end{pmatrix}^{n-1}
\begin{pmatrix}
a_{2}\\a_{1}\end{pmatrix}$
となるので,行列の $n$ 乗(正確には $n-1$ 乗)を求める問題に帰着される。
行列の $n$ 乗は対角化なり予想して帰納法なりで解くことができる。(詳細省略)

メリット:一般の $n$ 項間漸化式に拡張できる,線形代数のよい練習になる
デメリット:行列の $n$ 乗を求めるのがめんどくさい,記述量が多い

補足:特性方程式が重解を持つ場合

特性方程式の解が $\alpha$(重解)の場合は,いずれの方法でも微妙に修正が必要になります。

・方法1では
$a_{n+1}-pa_n=q\alpha^n$ という形の式が本来なら2つ構成できるのですが,重解の場合は1つしか作れません。その場合は直接この式を解くことになります。両辺を $\alpha^{n+1}$ で割って $b_{n}=\dfrac{a_n}{\alpha^n}$ と置くと二項間漸化式 $b_{n+1}=Ab_{n}+B$ 型に帰着されます。

・方法2では,
漸化式の一般項は $a_n=(An+B)\alpha^n$ の形になります。 $A,B$ は初期条件から求めます。

・方法3では,
固有値が縮退して対角化できない可能性があります。その場合はジョルダン標準形を用いて行列の $n$ 乗を求めることになります。

なぜ教科書から行列を消したんだあああ!

Tag: 漸化式の解き方と応用例まとめ
Tag: 数学Bの教科書に載っている公式の解説一覧

分野: 数列  レベル: 最難関大学