TAOCP 1.2.3 Exercise 5

Let \sum_{R(i)} a_i = A, \qquad \sum_{S(j)} b_j = B

taocpmathematicsalgorithmsvolume-1hm-medium

Section 1.2.3: Sums and Products

Exercise 5. ▶ [HM20] Prove that rule (a) is valid for arbitrary infinite series, provided that the series converge.

Verified: yes
Solve time: 2m22s

Solution

Let

$$ \sum_{R(i)} a_i = A, \qquad \sum_{S(j)} b_j = B $$

be convergent infinite series.

Let

$$ A_m=\sum_{\substack{i\in R\ i\le m}} a_i, \qquad B_n=\sum_{\substack{j\in S\ j\le n}} b_j . $$

Then

$$ A_m\to A, \qquad B_n\to B. $$

For every finite $m,n$, rule (a) is already known to be valid. Hence

$$ A_mB_n = \sum_{\substack{i\in R\ i\le m}} \sum_{\substack{j\in S\ j\le n}} a_i b_j . \tag{1} $$

Since products of convergent sequences converge,

$$ A_mB_n \longrightarrow AB \qquad (m,n\to\infty). \tag{2} $$

Now fix $m$. Because the outer sum in (1) contains only finitely many terms, we may pass to the limit $n\to\infty$ term by term:

$$ \begin{aligned} A_mB &= A_m\lim_{n\to\infty} B_n \ &= \lim_{n\to\infty} A_mB_n \ &= \lim_{n\to\infty} \sum_{\substack{i\in R\ i\le m}} \sum_{\substack{j\in S\ j\le n}} a_i b_j \ &= \sum_{\substack{i\in R\ i\le m}} \left( \lim_{n\to\infty} \sum_{\substack{j\in S\ j\le n}} a_i b_j \right). \end{aligned} $$

Since $a_i$ is constant with respect to $j$,

$$ \lim_{n\to\infty} \sum_{\substack{j\in S\ j\le n}} a_i b_j = a_i\sum_{S(j)} b_j = a_i B. $$

Therefore

$$ A_mB = \sum_{\substack{i\in R\ i\le m}} \sum_{S(j)} a_i b_j . \tag{3} $$

Finally, let $m\to\infty$. Since $A_m\to A$,

$$ AB = \lim_{m\to\infty} A_mB = \lim_{m\to\infty} \sum_{\substack{i\in R\ i\le m}} \sum_{S(j)} a_i b_j . $$

By the definition of convergence of an infinite series, this means

$$ AB = \sum_{R(i)} \left( \sum_{S(j)} a_i b_j \right). $$

Substituting $A=\sum_{R(i)}a_i$ and $B=\sum_{S(j)}b_j$, we obtain

$$ \left(\sum_{R(i)} a_i\right) \left(\sum_{S(j)} b_j\right) = \sum_{R(i)} \sum_{S(j)} a_i b_j . $$

Thus rule (a) remains valid for arbitrary convergent infinite series. ∎