2項間漸化式の解法(a(n+1) = p a(n) + q 型)


例題：漸化式 a_{n+1}=p\,a_{n}+q (n=1,2,3,\cdots) の一般項を求めよ。
回答：以下p≠0とする。
与えられた漸化式の両辺を p^{n+1} で割り算すると次の式を得る:
　(Eq.1)　　\large\frac{a_{n+1}}{p^{n+1}}=\frac{a_{n}}{p^{n}}+\frac{q}{p^{n+1}}.
ここで \large b_{n}:=\frac{a_{n}}{p^{n}} とおくと次の漸化式を得る:
　(Eq.1')　　\large b_{n+1}=b_{n}+\frac{q}{p^{n+1}}.
さてさてこのb_{n}の漸化式を逐次代入で解くと
　(Eq.2)　　\Large\begin{eqnarray}b_{n}&=&b_{n-1}+\frac{q}{p^{n}}\\&=&\left(b_{n-2}+\frac{q}{p^{n-1}}\right)+\frac{q}{p^{n}}\\&=&b_{n-2}+\frac{q}{p^{n-1}}+\frac{q}{p^{n}}\\&=&\left(b_{n-3}+\frac{q}{p^{n-2}}\right)+\frac{q}{p^{n-1}}+\frac{q}{p^{n}}\\&\cdots&\\&=&b_1+\frac{q}{p^{2}}+\frac{q}{p^{3}}+\cdots+\frac{q}{p^{n-1}}+\frac{q}{p^{n}}\\&=&\frac{a_1}{p}+\frac{q}{p^{2}}+\frac{q}{p^{3}}+\cdots+\frac{q}{p^{n-1}}+\frac{q}{p^{n}}\end{eqnarray}
この最後の行の式に p^n を掛け算して
　(Eq.3)　　\large\begin{eqnarray}a_{n}&=&a_1p^{n-1}+qp^{n-2}+qp^{n-3}+\cdots+qp+q\end{eqnarray}
ここでこの式の第2項から第n項までの等比数列の和を計算して整理すると、数列{a_{n}}の一般項を得る:
　(Eq.4)　　p≠1のとき \Large\begin{eqnarray}a_{n}=a_1p^{n-1}+q\frac{1-p^{n-1}}{1-p}=\left(a_1-\frac{q}{1-p}\right)p^{n-1}+\frac{q}{1-p}\end{eqnarray}
　(Eq.5)　　p＝1のとき \large a_{n}=a_1+(n-1)q