TAOCP 1.2.3 Exercise 22

Exercise 22. ▶ [20] State the appropriate analogs of Eqs. (5), (7), (8), and (11) for products instead of sums.

Verified: yes
Solve time: 1m44s

Solution

The required product analogs are obtained by replacing sums with products and interpreting repeated factors with multiplicity.

The analog of Eq. (5) is

$$ \prod_{R(i)} a_i = \prod_{R(j)} a_j = \prod_{R(p(j))} a_{p(j)}. $$

Here $p$ is a permutation of the indices satisfying the same condition as in Eq. (5): for each integer $i$ satisfying $R(i)$, there is exactly one integer $j$ such that $p(j)=i$. Thus the factors appearing in the products are the same, only written in a different order.

The analog of Eq. (7) is

$$ \prod_{R(i)} \prod_{S(j)} a_{ij} = \prod_{S(j)} \prod_{R(i)} a_{ij}. $$

Both sides represent the product of all factors $a_{ij}$ for which $R(i)$ and $S(j)$ are true. Since multiplication is associative and commutative, the order of formation of the products is irrelevant.

The analog of Eq. (8) is

$$ \prod_{R(i)} (b_i c_i) = \left(\prod_{R(i)} b_i\right) \left(\prod_{R(i)} c_i\right). $$

To justify this identity, expand the product on the left:

$$ \prod_{R(i)} (b_i c_i) = (b_{i_1}c_{i_1})(b_{i_2}c_{i_2})\cdots = (b_{i_1}b_{i_2}\cdots)(c_{i_1}c_{i_2}\cdots), $$

where $i_1,i_2,\dots$ are the indices satisfying $R(i)$. Rearranging factors gives exactly

$$ \left(\prod_{R(i)} b_i\right) \left(\prod_{R(i)} c_i\right). $$

The analog of Eq. (11) is

$$ \left(\prod_{R(j)} a_j\right) \left(\prod_{S(j)} a_j\right) = \left(\prod_{R(j)\text{ or }S(j)} a_j\right) \left(\prod_{R(j)\text{ and }S(j)} a_j\right). $$

To verify this identity, consider a fixed index $j$.

If exactly one of $R(j)$ or $S(j)$ is true, then $a_j$ appears once on each side.
If both $R(j)$ and $S(j)$ are true, then $a_j$ appears twice on each side.
If neither condition is true, then $a_j$ appears on neither side.

Hence every factor $a_j$ occurs with the same multiplicity on both sides, so the two products are equal.