漸化式の解法あれこれ： a_{n+1} = p a_n + q

今回は以下の形の初項、漸化式で定義される数列の一般項を求めます：

　　 ${ \displaystyle \begin{align*} \begin{cases} a_1 \quad= a \\ a_{n+1} = p a_n + q \end{cases} \end{align*} }$

${ p,\,q }$ は定数とします。　漸化式の問題の基本中の基本ですね。

${ p \ne 1 }$ の場合

まずは ${ p \ne 1 }$ の場合。　このときは特性方程式の解 ${ \alpha }$ を使って等比数列を構成し、一般項を求めます。

特性方程式

漸化式で ${ a_n,\,a_{n+1} }$ をともに ${ \alpha }$ とおくと特性方程式が得られます：

　　 ${ \displaystyle \begin{align*} \alpha = p \alpha + q \end{align*} }$

${ p \ne 1 }$ のとき、これは簡単に解けて

　　 ${ \displaystyle \begin{align*} \alpha = - \frac{q}{p-1} \end{align*} }$

を得ます。

数列 ${ b_n }$

漸化式と特性方程式より

　　 ${ \displaystyle \begin{align*} a_{n+1} &= p a_n + q \\ \alpha &= p \alpha\,\, + q \end{align*} }$

辺々をそれぞれ引くと

　　 ${ \displaystyle \begin{align*} a_{n+1} - \alpha = p (a_n - \alpha) \end{align*} }$

ここで

　　 ${ \displaystyle \begin{align*} b_n = a_n - \alpha \end{align*} }$

とおくと、数列 ${ b_n }$ の初項と漸化式は

　　 ${ \displaystyle \begin{align*} \begin{cases} b_1 \quad= a - \alpha \\ b_{n+1} = pb_n \end{cases} \end{align*} }$

よって ${ b_n }$ は等比数列であることが分かり、その一般項は

　　 ${ \displaystyle \begin{align*} b_n = (a - \alpha) p^{n-1} \end{align*} }$

と求まります。

${ a_n }$ の一般項

${ a_n }$ の一般項は ${ b_n }$ の一般項から簡単に求まって

　　 ${ \displaystyle \begin{align*} a_n &= b_n + \alpha \\ &= (a - \alpha) p^{n-1} + \alpha \\ &= \left(a + \frac{q}{p-1}\right)p^{n-1} - \frac{q}{p-1} \end{align*} }$

よって

　　 ${ \displaystyle \begin{align*} a_n = \left(a + \frac{q}{p-1}\right)p^{n-1} - \frac{q}{p-1} \end{align*} }$

${ p = 1 }$ のとき

${ p = 1 }$ のとき、初項と漸化式は

　　 ${ \displaystyle \begin{align*} \begin{cases} a_1 \quad = a \\ a_{n+1} = a_n + q \end{cases} \end{align*} }$

となりますが、これは ${ a_n }$ が初項 ${ a }$ 、公差 ${ q }$ の等差数列であることを示しています。　よって一般項は

　　 ${ \displaystyle \begin{align*} a_n = a + q(n-1) \end{align*} }$

となります。

結果

結果をまとめると

　　 ${ \displaystyle \begin{align*} a_n = \begin{cases} \left(a + \dfrac{q}{p-1}\right)p^{n-1} - \dfrac{q}{p-1} & (p\ne 1) \\[4mm] a + q(n - 1) & (p = 1) \end{cases} \end{align*} }$

ちなみに初項が第0項で与えられている場合（ ${ a_0 = a }$ ）は以下のようになります：

　　 ${ \displaystyle \begin{align*} a_n = \begin{cases} \left(a + \dfrac{q}{p-1}\right)p^n - \dfrac{q}{p-1} & (p\ne 1) \\[4mm] a + qn & (p = 1) \end{cases} \end{align*} }$