14.6 ダブルトラブル

総和の総和を二重総和 (double summation) と呼ぶ。二重総和の評価は厄介だと思うかもしれない。その直感が正しいケースもある一方で、そうだとしてもすべきことは単純である ── 最初に内側の総和を評価して閉形式の式に置き換え、それから (内部に総和が無くなった) 外側の総和を評価すればいい。例えば¹:

\[ \begin{align*} \small\sum_{n=0}^{\infty} \left( y^{n} \sum_{i=n}^{n} x^{i} \right) &= \sum_{n=0}^{\infty} \left( y^{n} \frac{1 - x^{n+1}}{1 - x} \right) && (\text{等式 } \href{/mcs/counting/sums_and_asymptotics//#eq-14-2}{(14.2)} \text{ より}) \\ &= \left( \frac{1}{1-x} \right) \sum_{n=0}^{\infty} y^{n} - \left( \frac{1}{1-x} \right) \sum_{n=0}^{\infty} y^{n}x^{n+1} && \\ &= \frac{1}{(1 - x)(1 - y)} - \left( \frac{x}{1-x} \right) \sum_{n=0}^{\infty} (xy)^{n} && (\text{定理 }\href{/mcs/counting/sums_and_asymptotics/value_of_an_annuity/#theorem-14-1-1}{14.1.1} \text{ より}) \\ &= \frac{1}{(1 - x)(1 - y)} - \frac{x}{(1 - x)(1 - xy)} && (\text{定理 }\href{/mcs/counting/sums_and_asymptotics/value_of_an_annuity/#theorem-14-1-1}{14.1.1} \text{ より}) \\[15pt] &= \frac{(1 - xy) - x(1 - y)}{(1 - x)(1 - y)(1 - xy)} && \\[10pt] &= \frac{1 - x}{(1 - x)(1 - y)(1 - xy)} && \\[10pt] &= \frac{1}{(1 - y)(1 - xy)} && \end{align*} \]

内側の総和を閉形式に変換できないとき、二重総和でのみ利用できる特殊な手法として加算の順序の交換がある。例えば、最初の \(n\) 個の調和数の和 \(S\) を求めたいとする:

\[ S = \sum_{k=1}^{n} H_{k} = \sum_{k=1}^{n} \sum_{j=1}^{k} \frac{1}{j} \tag{14.27}\]

この総和の近似を求めるだけなら、定理 14.3.2 と等式 \(\text{(14.21)}\) を使えば \(S\) が次の値に近いと分かる:

\[ \int_{1}^{n} \ln x \, dx = \left. \text{\large\mathstrut} \left( x \ln x - x \right) \right|_{1}^{n} = n \ln n - n + 1 \]

しかし、加算の順序を適切に交換すると \(S\) を閉形式に変換できる。足される項 \(1/j\) と、それを特定する添え字の組 \((k, j)\) をまとめた表を次に示す:

\[ \def\arraystretch{1.2}\begin{array}{cc|ccccccc} & & j & & & & & \\ & & 1 & 2 & 3 & 4 & \cdots & n \\ \hline k & 1 & 1 & & & & & \\ & 2 & 1 & 1/2 & & & & \\ & 3 & 1 & 1/2 & 1/3 & & & \\ & 4 & 1 & 1/2 & 1/3 & 1/4 & & \\ & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \\ & 5 & 1 & 1/2 & 1/3 & 1/4 & \cdots & 1/n \end{array} \]

等式 \(\text{(14.27)}\) の総和は、この表に書かれた数字の行ごとの和を全て足す計算を意味する。そうする代わりに、列ごとに計算した和を全て足すことでも \(S\) を計算できる。表を参考にすれば、二重和は次のように変形できる:

\[ \begin{align*} S = \sum_{k=1}^{n} H_{k} &= \sum_{k=1}^{n} \sum_{j=1}^{k} \frac{1}{j} \\ &= \sum_{j=1}^{n} \sum_{k=j}^{n} \frac{1}{j} \\ &= \sum_{j=1}^{n} \frac{1}{j} \sum_{k=j}^{n} 1 \\ &= \sum_{j=1}^{n} \frac{1}{j} (n - j + 1) \\ &= \sum_{j=1}^{n} \frac{n + 1}{j} - \sum_{j=1}^{n} \frac{j}{j} \\ &= (n + 1) \sum_{j=1}^{n} \frac{1}{n} - \sum_{j=1}^{n} 1 \\ &= (n + 1) H_{n} - n \tag{14.28} \end{align*} \]

OK、この例は確かに厄介だ。しかし、各変形で適用される操作はどれも単純である。次の例とは話が違う！ ↩︎