選択ソートの計算量を求めるときに式の導出過程がイミフだったのでおべんきょしたメモ。

等差数列と初項・末項・公差・項数


$1 + 2 + 3 + … n-1 + n$

という数列があったとする。この時に初項・末項・公差・項数とはそれぞれ下記を意味する。

  • 初項: はじめの値。つまり1
  • 末項: 最後の値。つまりn
  • 公差: それぞれの数値の差。つまり1
  • 項数: 数列の数。つまりn

公差が一定の差である数列を等差数列という。

等差数列の和


求め方1

等差数列は初項と末項の順序を逆転させたものを足して2で割れば求めることができる。例えば…

$1 + 2 + 3 + 4$ という数列があるとして、この数列と逆転させた数列$4 + 3 + 2 + 1$ を足して2で割ると数列の和を求めることができる。つまり…

$2S = 5 + 5 + 5 + 5 = 20$ となるので $S = \frac{ 20 }{ 2 } $ となる。

求め方2

初項 $a$,公差$d$, 項数$n$, 末項$l$ とした場合に等差数列の和($Sn$)は下記のようになる。

$Sn = a + (a + d) + (a + 2d) + (a + 3d) + … + (l - d) + l$

これを逆転させると…

$Sn = l + (l - d) + (l - 2d) + (l - 3d) + … + (a - d) + a$

となる。

この2つを足すと…$(a + l)$ が $n$ あることになるので $2Sn = n(a + l)$ になる。つまり $\frac{ na + ln }{ 2 } $ となる。

Σ


$Σ$ は雑に説明すると上記のような数列を簡潔に表現するためのアレ。始めに記した等差数列を $Σ$ で表現すると下記のようになる。

$\displaystyle \sum_{ i = 1 }^{ n } i = 1 + 2 + 3 + … n-1 + n$

  • $n$ が項数
  • $i$ は初項

等差数列とΣ


等差数列の和は前述のとおり $\frac{ na + ln }{ 2 } $ なので、これを $Σ$ で表現すると下記のようになる。

$\displaystyle \sum_{ i = 1 }^{ n } i = \frac{ na + ln }{ 2 } $

記した等差数列 $1 + 2 + 3 + … n-1 + n$ とそれを逆転させた数列はそれぞれ…

$Sn = 1 + (1 + 1) + (1 + 2) + (1 + 3) + … + (n - 1) + n$
$Sn = n + (n - 1) + (n - 2) + (n - 3) + … + (1 + 1) +1$

となるのでこれらを足すと $2Sn = n + (n + 1)$ となる。これを $Σ$ に当てはめると下記のようになる。

$\displaystyle \sum_{ i = 1 }^{ n } i = \frac{ n^2 + n }{ 2 } $

参考


下記のサイトを参考にさせて頂きました。ありがとうございました。