【基本】漸化式

ここでは、数列の分野で重要な「漸化式」について見ていきます。

【広告】

漸化式

今までに扱ってきた数列には、差が一定の等差数列、比が一定の等比数列、そして、各項の差が等差数列や等比数列になっている階差数列がありました。

これらの数列を扱ってきたときには、まず数列の一部分を見て、規則性を把握して、その後で一般項を求める、というのが王道の流れでした。

ただ、この「数列の一部分から規則性を把握」というのは、少しあいまいです。\[ 2,4,8,16,\cdots \]となっているからと言って、等比数列と断言するのはあまり厳密ではありません(といいつつ、もし試験でこの形で出題されれば、等比数列だと考えて解くことになりますが)。

そこで、規則性を厳密に表現するために、次のような式が使われます。\[ a_{n+1}=a_n+n \]これは、 $n$ 番目と $(n+1)$ 番目がどういう関係か、を表しています。この漸化式があれば、数列の各項が次々と決まっていきます。

例えば、数列 $\{a_n\}$ が、\[ a_1=1,\ a_{n+1}=a_n+n \]を満たしていたとします(n は正の整数)。2つ目の式で、 $n=1$ とすると
\begin{eqnarray}
a_2
&=&
a_1+1
&=&
2
\end{eqnarray}となります。また、 $n=2$ とすれば
\begin{eqnarray}
a_3
&=&
a_2+2
&=&
4
\end{eqnarray}となります。 $a_2$ は先ほど求めたので、代入することができるわけですね。 $n=3$ とすれば
\begin{eqnarray}
a_4
&=&
a_3+3
&=&
7
\end{eqnarray}となります。以下、同様にしていけば、数列の各項が次々と計算でき、すべての項が1通りに決まっていきます。

この $a_{n+1}=a_n+n$ のように、それ以前の項を決めれば、次の項がただ1通りに決める規則を表した式を、漸化式(recurrence relation) といいます。この方法を使えば、「数列の一部から規則を把握する」ことが不要となり、あいまいさがなくなります。

ちなみに、「漸化式」の「漸」は、「だんだん進む・少しずつ進む」といった意味があります。各項が1つ1つ求められていくことを表しています。

漸化式から何をするか

引き続き、\[ a_1=1,\ a_{n+1}=a_n+n \]を満たしている数列 $\{a_n\}$ について考えましょう。

2つ目の式で、 $n=1$ として計算、 $n=2$ として計算、 $n=3$ として計算、…としていけば、どの項も順番に求めていくことができます。

しかし、逆にいえば、一発でだいぶ先の方を求めることはできないわけですね。例えば、 $a_{100}$ を求めたければ、その手前の $a_{99}$ が必要です。これを求めるには $a_{98}$ が必要で、結局、 $99$ 項目までをすべて順番に求めなければならず、そしてようやく漸化式に $n=99$ を代入して $a_{100}$ が求められる、というわけです。

これはめんどくさいです。普通はこんなことはしません。いくつかの漸化式については、工夫して計算することにより、一般項を求めることができます。つまり、\[ a_1=1,\ a_{n+1}=a_n+n \]という漸化式を用いた状態から(漸化式について学べば)\[ a_n=\frac{1}{2}(n^2-n+2) \]と求めることができます。(実際に n に値を代入すると、合っていることが確認できます)

おわりに

ここでは、漸化式そのものについての紹介を行いました。今後は、いろいろな漸化式から、一般項を求める方法を見ていくことになります。