TAOCP 1.2.3 Exercise 29

Define S=\sum_{i=0}^n \sum_{j=0}^i \sum_{k=0}^j a_i a_j a_k.

taocpmathematicsalgorithmsvolume-1math-hard

Section 1.2.3: Sums and Products

Exercise 29. ▶ [M30] (a) Express $\sum_{i=0}^n \sum_{j=0}^i \sum_{k=0}^j a_i a_j a_k$ in terms of the multiple-sum notation explained at the end of the section. (b) Express the same sum in terms of $\sum_{i=0}^n a_i$, $\sum_{i=0}^n a_i^2$, and $\sum_{i=0}^n a_i^3$ [see Eq. (13)].

Verified: yes
Solve time: 38s

Setup

Define

$$ S=\sum_{i=0}^n \sum_{j=0}^i \sum_{k=0}^j a_i a_j a_k. $$

Part (a) asks for an expression of $S$ in the multiple-sum notation introduced at the end of the section. Part (b) asks for an expression of $S$ in terms of

$$ \sum_{i=0}^n a_i,\qquad \sum_{i=0}^n a_i^2,\qquad \sum_{i=0}^n a_i^3. $$

Solution

(a)

The conditions on the indices are

$$ 0\le k\le j\le i\le n. $$

Hence the required multiple-sum notation is

$$ \boxed{ S=\sum_{0\le k\le j\le i\le n} a_i a_j a_k. } $$

(b)

Let

$$ T=\left(\sum_{i=0}^n a_i\right)^3. $$

By repeated use of the distributive law (4),

$$ T=\sum_{i=0}^n \sum_{j=0}^n \sum_{k=0}^n a_i a_j a_k. $$

Every ordered triple $(i,j,k)$ with $0\le i,j,k\le n$ belongs to exactly one of the following classes:

  1. $i=j=k$;
  2. exactly two of $i,j,k$ are equal;
  3. $i,j,k$ are all distinct.

The contribution of the first class is

$$ \sum_{i=0}^n a_i^3. $$

For the second class, fix distinct integers $r,s$. The monomial $a_r^2a_s$ occurs in exactly three ordered forms:

$$ a_r a_r a_s,\qquad a_r a_s a_r,\qquad a_s a_r a_r. $$

Hence the total contribution of all such terms is

$$ 3\sum_{\substack{0\le r,s\le n\ r\ne s}} a_r^2a_s. $$

For the third class, fix distinct integers $r,s,t$. The monomial $a_ra_sa_t$ occurs in exactly six ordered forms, corresponding to the six permutations of $(r,s,t)$. Hence the total contribution is

$$ 6\sum_{0\le t<s<r\le n} a_ra_sa_t. $$

Therefore

$$ T = \sum_{i=0}^n a_i^3 + 3\sum_{\substack{0\le r,s\le n\ r\ne s}} a_r^2a_s + 6\sum_{0\le t<s<r\le n} a_ra_sa_t. \eqno(1) $$

Now decompose $S$ according to the same three cases. The condition $k\le j\le i$ selects exactly one ordering of each triple.

If $i=j=k$, the contribution is

$$ \sum_{i=0}^n a_i^3. $$

If exactly two indices are equal, there are two possible forms:

$$ i=j>k, \qquad i>j=k. $$

Thus the contribution is

$$ \sum_{0\le k<i\le n} a_i^2a_k + \sum_{0\le j<i\le n} a_i a_j^2. $$

By renaming indices in the second sum,

$$ \sum_{0\le j<i\le n} a_i a_j^2 = \sum_{0\le r<s\le n} a_s a_r^2. $$

Hence the two sums together equal

$$ \sum_{\substack{0\le r,s\le n\ r\ne s}} a_r^2a_s. $$

If all three indices are distinct, the inequalities force

$$ k<j<i, $$

so the contribution is

$$ \sum_{0\le k<j<i\le n} a_i a_j a_k. $$

Consequently,

$$ S = \sum_{i=0}^n a_i^3 + \sum_{\substack{0\le r,s\le n\ r\ne s}} a_r^2a_s + \sum_{0\le k<j<i\le n} a_i a_j a_k. \eqno(2) $$

Multiply (2) by $6$:

$$ 6S = 6\sum_{i=0}^n a_i^3 + 6\sum_{\substack{0\le r,s\le n\ r\ne s}} a_r^2a_s + 6\sum_{0\le k<j<i\le n} a_i a_j a_k. \eqno(3) $$

Subtract (1) from (3):

$$ 6S-T = 5\sum_{i=0}^n a_i^3 + 3\sum_{\substack{0\le r,s\le n\ r\ne s}} a_r^2a_s. \eqno(4) $$

Now

$$ \left(\sum_{i=0}^n a_i^2\right) \left(\sum_{j=0}^n a_j\right) = \sum_{i=0}^n a_i^3 + \sum_{\substack{0\le r,s\le n\ r\ne s}} a_r^2a_s, $$

by the distributive law (4). Therefore

$$ \sum_{\substack{0\le r,s\le n\ r\ne s}} a_r^2a_s = \left(\sum_{i=0}^n a_i^2\right) \left(\sum_{j=0}^n a_j\right) - \sum_{i=0}^n a_i^3. $$

Substituting into (4) gives

$$ 6S-T = 5\sum_{i=0}^n a_i^3 + 3\left[ \left(\sum_{i=0}^n a_i^2\right) \left(\sum_{j=0}^n a_j\right) - \sum_{i=0}^n a_i^3 \right]. $$

Hence

$$ 6S-T = 2\sum_{i=0}^n a_i^3 + 3\left(\sum_{i=0}^n a_i^2\right) \left(\sum_{j=0}^n a_j\right). $$

Since

$$ T=\left(\sum_{i=0}^n a_i\right)^3, $$

we obtain

$$ \boxed{ \sum_{i=0}^n \sum_{j=0}^i \sum_{k=0}^j a_i a_j a_k = \frac16 \left(\sum_{i=0}^n a_i\right)^3 + \frac12 \left(\sum_{i=0}^n a_i^2\right) \left(\sum_{i=0}^n a_i\right) + \frac13 \sum_{i=0}^n a_i^3. } $$

Verification

Take $n=1$. Then

$$ S = a_0^3+a_1a_0^2+a_1^2a_0+a_1^3. $$

The formula gives

$$ \frac16(a_0+a_1)^3 + \frac12(a_0^2+a_1^2)(a_0+a_1) + \frac13(a_0^3+a_1^3). $$

Expanding,

$$ \begin{aligned} &\frac16(a_0^3+3a_0^2a_1+3a_0a_1^2+a_1^3) \ &\qquad +\frac12(a_0^3+a_0^2a_1+a_0a_1^2+a_1^3) +\frac13(a_0^3+a_1^3). \end{aligned} $$

The coefficients combine to give

$$ a_0^3+a_0^2a_1+a_0a_1^2+a_1^3, $$

which agrees with the direct computation.

Notes

The result is the cubic analogue of equation (13). In general, sums over weakly ordered indices can be expressed through symmetric polynomials by counting the multiplicities with which monomials occur in unrestricted products.