第 14 章 総和と漸近記法
総和と総乗はアルゴリズムの解析、金融分野の応用、物理学の問題、確率システムで頻繁に姿を現す。例えば、定理 2.2.1 からは次の等式が分かる:
もちろん、左辺の和は添え字を使った総和で簡潔に表現できる:
しかし、右辺の \(n(n+1)/2\) は簡潔であるだけではなく計算が簡単でもある。さらに、和が大きくなる速さといった性質も明確になる。添え字を使った総和や総乗 ── そして、便利な一方で問題を起こしがちな三つのドット ── を使わない \(n(n + 1)/2\) のような式を閉形式 (closed form) の式と呼ぶ。閉形式の式は閉じた式とも呼ぶ。
別の例として、問題 5.4 で示したように、幾何級数 (geometric series) の値は閉形式で表せる:
等式 \(\text{(14.2)}\) の左辺を計算するには \(n\) 回の加算と \(1 + 2 + \cdots + (n-1) = (n-1)n/2\) 回の乗算が必要になるのに対して、右辺の計算では高速冪乗を使えば最大でも \(2\log n\) 回の乗算、\(1\) 回の除算、そして \(2\) 回の減算しか必要にならない。さらに、閉形式があると \(n\) が大きくなったとき和の振る舞いを簡単に確認できる。
等式 \(\text{(14.1)}\), \(\text{(14.2)}\) の正しさは数学的帰納法で簡単に検証できる。しかし、数学的帰納法を使った証明からはこういった式を何のヒントもない状態から見つける方法は分からない。こういった式を見つける問題では数学の知識と技法の両方が利用される。この二つが本章のテーマとなる。
最初の例として、読者も身近に感じるはずのアニュイティ (annuity) と呼ばれる金融商品の価値を考える。この問題では大きくて複雑な見た目をした総和が登場する。その後は総和を閉形式で表すための手法をいくつか紹介する。その一つはアニュイティの価値の計算にも適用できる。総和を閉形式で表せないケースもあるので、そういった状況で利用できる総和の優れた上界と下界を見つける一般的な手法も説明する。
これから紹介する総和を閉形式に書き換える手法は総乗にも適用できる: 対数を取れば総乗は総和になる。例えば章の後半では、この考え方を使って次の階乗関数 (factorial function) の優れた閉形式の近似を得る:
章の最後では漸近記法を議論する。特に「ビッグオー」記法と呼ばれる記法に焦点を当てる。総和や総乗を閉形式で厳密に表せないとき誤差項を見積もるために漸近記法はよく利用される。また、総和や総乗が大きくなる速さの度合いを表現するときにも利用される。