TAOCP 1.2.3 Exercise 32

Exercise 32. [M20] Prove that

$$\prod_{j=1}^n \sum_{i=1}^m a_{ij} = \sum_{1 \le i_1, \ldots, i_n \le m} a_{i_1 1} \ldots a_{i_n n}.$$

Verified: yes
Solve time: 29s

Solution

We proceed by induction on $n$.

Base case: Let $n = 1$. Then the left-hand side is

$\prod_{j=1}^1 \sum_{i=1}^m a_{i1} = \sum_{i=1}^m a_{i1}.$

The right-hand side is

$\sum_{1 \le i_1 \le m} a_{i_1 1} = \sum_{i=1}^m a_{i1},$

so the identity holds for $n = 1$.

Inductive step: Assume the identity holds for some $n \ge 1$, that is,

$\prod_{j=1}^n \sum_{i=1}^m a_{ij} = \sum_{1 \le i_1, \ldots, i_n \le m} a_{i_1 1} a_{i_2 2} \cdots a_{i_n n}. \eqno(*)$

We must show it holds for $n+1$. Consider

$\prod_{j=1}^{n+1} \sum_{i=1}^m a_{ij} = \left( \prod_{j=1}^{n} \sum_{i=1}^m a_{ij} \right) \left( \sum_{i=1}^m a_{i, n+1} \right).$

By the induction hypothesis $(*)$, this is

$\left( \sum_{1 \le i_1, \ldots, i_n \le m} a_{i_1 1} a_{i_2 2} \cdots a_{i_n n} \right) \left( \sum_{i_{n+1}=1}^m a_{i_{n+1}, n+1} \right).$

Applying the distributive law for products of sums (Eq. (4)), we have

$\sum_{1 \le i_1, \ldots, i_n \le m} \sum_{i_{n+1}=1}^m a_{i_1 1} a_{i_2 2} \cdots a_{i_n n} a_{i_{n+1}, n+1}.$

Combining the double sum into a single $n+1$-fold sum over all sequences $(i_1, \ldots, i_{n+1})$ with $1 \le i_j \le m$, we obtain

$\sum_{1 \le i_1, \ldots, i_{n+1} \le m} a_{i_1 1} a_{i_2 2} \cdots a_{i_{n+1}, n+1},$

which is exactly the right-hand side of the formula for $n+1$.

By induction, the identity holds for all $n \ge 1$. This completes the proof. ∎