TAOCP 1.2.3 Exercise 26

Section 1.2.3: Sums and Products

Exercise 26. [25] Show that $\prod_{i=0}^n \prod_{j=0}^i a_i a_j$ may be expressed in terms of $\prod_{i=0}^n a_i$ by manipulating the $\prod$-notation as stated in exercise 22.

Verified: yes
Solve time: 35s

---

Solution

Let

$$ P=\prod_{i=0}^n \prod_{j=0}^i a_i a_j. $$

We manipulate the product notation by the analogues of rules (a), (b), (c), and (d).

First separate the factors depending on $i$ from those depending on $j$:

$$ P = \prod_{i=0}^n \prod_{j=0}^i (a_i a_j) = \left(\prod_{i=0}^n \prod_{j=0}^i a_i\right) \left(\prod_{i=0}^n \prod_{j=0}^i a_j\right). $$

Consider the first factor. For fixed $i$, the index $j$ runs through the values $0,1,\ldots,i$, hence there are $i+1$ identical factors $a_i$. Therefore

$$ \prod_{j=0}^i a_i = a_i^{i+1}, $$

and consequently

$$ \prod_{i=0}^n \prod_{j=0}^i a_i = \prod_{i=0}^n a_i^{i+1}. $$

Now consider the second factor:

$$ \prod_{i=0}^n \prod_{j=0}^i a_j. $$

By the product analogue of Eq. (10),

$$ \prod_{i=0}^n \prod_{j=0}^i a_j = \prod_{j=0}^n \prod_{i=j}^n a_j. $$

For fixed $j$, the index $i$ runs through the values $j,j+1,\ldots,n$, a total of

$$ n-j+1 $$

values. Hence

$$ \prod_{i=j}^n a_j = a_j^{,n-j+1}, $$

so

$$ \prod_{j=0}^n \prod_{i=j}^n a_j = \prod_{j=0}^n a_j^{,n-j+1}. $$

Therefore

$$ P = \left(\prod_{i=0}^n a_i^{i+1}\right) \left(\prod_{j=0}^n a_j^{,n-j+1}\right). $$

Renaming the index $j$ to $i$ in the second product by rule (b),

$$ P = \prod_{i=0}^n a_i^{i+1} \prod_{i=0}^n a_i^{,n-i+1}. $$

Using the product analogue of rule (a),

$$ P = \prod_{i=0}^n a_i^{(i+1)+(n-i+1)} = \prod_{i=0}^n a_i^{n+2}. $$

Finally,

$$ \prod_{i=0}^n a_i^{n+2} = \left(\prod_{i=0}^n a_i\right)^{n+2}. $$

Thus

$$ \boxed{ \prod_{i=0}^n \prod_{j=0}^i a_i a_j = \left(\prod_{i=0}^n a_i\right)^{n+2} }. $$

∎