2.4 和 $\sum$ の計算

一見漸化式と関係なさそうでも、 漸化式を用いて計算すると便利というものが結構あります。

例えば数列 $\{a_j\}$ の和 $s=\dsp\sum_{j=1}^n a_j$ は、 部分和

$$s_j:=\sum_{k=1}^j a_k$$

を導入すると、数列 $\{s_j\}$ の第 $n$ 項である、 すなわち $s=s_n$ ですが、$\{s_j\}$ は

$$s_1=a_1,\quad s_{j}=s_{j-1}+a_{j}$$   $$\mbox{($j\ge 2$)}$$

あるいは

$$s_0=0,\quad s_{j}=s_{j-1}+a_{j}$$   $$\mbox{($j\ge 1$)}$$

という漸化式で定義することができます。 例えば

s=0
for j=1 to n
    s=s+($a_j$ を計算する式)
next j
print s

のようなコード¹で $s_n$ が計算できます。