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

Aru

確率・統計をやっていると漸化式も結構出てくるのでその復習を兼ねて$a_{n+1} = a_n + f(n)$のパターンについて解説します

漸化式 $a_{n+1} = a_n + f(n)$

$$ a_{n+1} = a + \sum_{k=1}^{n-1}{f(k)} $$

Contents

漸化式とは
一般項を求める
例題
終わりに

漸化式とは

漸化式とは、隣り合う数列の項の間で成り立つ関係式です。

$$a_{n+1} = a_{n}…$$のように、右辺と左辺に隣り合う数列の項が出てくるものになります。

漸化式を解くとは、漸化式から「一般項を導き出す」ことです。ここでは、簡単な漸化式、

$a_{n+1} = a_n + f(n)$

の一般項を求めてみます

一般項を求める

$$a_{n+1} = a_n + f(n)$$

この形は、$a_1 = a$とすると、

$$ \begin{eqnarray} a_1 & = & a\\ a_2 & = & a_1 + f(1) & = & a + f(1) \\ a_3 & = & a_2 + f(2) & = & a + f(1) + f(2) \\ a_4 & = & a_3 + f(3) & = & a + f(1) + f(2) + f(3) \\ : \end{eqnarray} $$ となります。

これを整理すると以下の式が一般項として求まります。

$$ a_{n+1} = a + \sum_{k=1}^{n-1}{f(k)} $$

例題

ここで、実際の例として以下を考えてみます。

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

先ほどの結果に当てはめると、一般項は以下のようになります。

$$ a_{n} = 1 + \sum_{k=1}^{n-1}{k^2} $$

ただ、$\sum$は展開して解答とすることが多いので、$ \sum_{k=1}^{n-1}{k^2}$を展開する必要があります。

シグマの計算については、「等比数列の公式」にも書いていますが、ここでは以下の公式を利用します。

$$
\sum_{k=1}^{n}k^2=\frac{n\left( n+1 \right) \left( 2n+1 \right)}{6}
$$

等比数列の公式

これを使うと、

$$ \begin{eqnarray} \sum_{k=1}^{n-1}k^2&=&\frac{(n-1)\left( (n-1)+1 \right) \left( 2(n-1)+1 \right)}{6} \\ &=&\frac{1}{6} (n-1)n(2n-1) \end{eqnarray} $$

なので、これを代入して、

$$ \begin{eqnarray} a_{n} &=& 1 + \sum_{k=1}^{n-1}{k^2}\\ &=& 1 + \frac{1}{6} (n-1)n(2n-1) \\ &=& 1 + \frac{1}{6}(n^2 – n)(2n-1) \\ &=& \frac{1}{6}(2n^3 -n^2 -2n^2 +n)+1\\ &=& \frac{1}{3}n^3 – \frac{1}{2}n^2+\frac{1}{6}n + 1\\ \end{eqnarray} $$

と一般項を求めることができます。