漸化式（３） a(n+2) = pa(n+1) + qa(n)

ここで説明する漸化式は以下の形の式になります。

解き方

$$ a_{n+2} = pa_{n+1} + qa_n $$

この形の数式は、以下の形に持っていきます。

この式を変形すると、以下のようになります。

$$ a_{n+2} = \left( \alpha + \beta \right) a_{n+1} – \alpha \beta a_n $$

この式を最初の式と比較すると、以下が成り立てば良いことが分かります。

$$
\begin{eqnarray}
p &=& \alpha + \beta \\
q &=& – \alpha \beta
\end{eqnarray}$$

これは、実は以下の２次方程式の解となります。

$$
x ^ 2 – p x – q = 0
$$

ということで、これを解けばよいことになります。

ここは、以下の式展開を考えればわかるかと思います

$$(x – \alpha)(x-\beta) = x^2 – (\alpha+\beta)x + \alpha\beta$$

(x – a)(x-b) = x^2 – (a+b)x + ab

また、この式は、以下のように変形できるます。

$$
x^2 = px + q
$$

これは

$$ \begin{eqnarray} a_{n+2} &=& x^2\\ a_{n+1} &=& x\\ a_n &=& 1 \end{eqnarray} $$

と置いた式に一致します。

個人的には、$x ^ 2 – p x – q = 0$の解になるというところが、すぐに思いつきません。言われればその通りなんですが、自分で気づくのは厳しいです。ここが数学センスの無いところなんでしょうね。

さて、αとβが求まれば、

$$ \begin{eqnarray} a_{n+2} – \alpha a_{n+1} &=& \beta \left( a_{n+1} – \alpha a_n \right)\\ a_{n+2} – \beta a_{n+1} &=& \alpha \left( a_{n+1} – \beta a_n \right) \end{eqnarray} $$

と、２つの式を作り、それぞれ等比数列として解きます。

$$ \begin{eqnarray} a_{n+1} – \alpha a_{n} &=& 初項_1 \beta^{n-1}\\ a_{n+1} – \beta a_{n} &=& 初項_2 \alpha^{n-1} \end{eqnarray} $$

あとは、この２つの式を引けば$a_{n+1}$が消えて$a_n$が求まります。

例題を解く

解き方がわかったので

特性方程式

$$
x ^ 2 = 5 x – 6
$$

を解くと、

$$
x = 2,3
$$

となるので、以下の２つの式が作れる。

$$ \begin{eqnarray} a_{n+2} – 2 a_{n+1} &=& 3 \left( a_{n+1} – 2 a_n \right)\\ a_{n+2} – 3 a_{n+1} &=& 2 \left( a_{n+1} – 3 a_n \right)\\ \end{eqnarray} $$

ここで、

$$ a_1 – 2a_0 = 10 – 2 = 8\\ a_1 – 3a_0 = 10 – 3 = 7\\ $$

から、

$$ \begin{eqnarray} a_{n+1} – 2 a_{n} &=& 8 \cdot 3^{n-1}\\ a_{n+1} – 3 a_{n} &=& 7 \cdot 2^{n-1}\\ \end{eqnarray} $$

２つの式を引くと、以下の一般項が得られる。

$$ a_{n} = 8 \cdot 3^{n-1} – 7 \cdot 2^{n-1}\\ $$

漸化式については、以下も参考にしてください。

あわせて読みたい

漸化式（２） a(n+1)=pa(n)+q

あわせて読みたい

漸化式 a(n+1) = a(n) + f(n)

ある/Aru

IT＆機械学習エンジニア/ファイナンシャルプランナー（CFP®)

XContact

専門分野は並列処理・画像処理・機械学習・ディープラーニング。プログラミング言語はC, C++, Go, Pythonを中心として色々利用。現在は、Kaggle, 競プロなどをしながら悠々自適に活動中