Deriving the Closed-Form of a Multi-Index Summation

1 Problem Statement

We seek a simple closed-form formula for the summation \( S(\triangleright) \), defined as the sum over the lower triangle (including the diagonal) of a symmetric square array:

\[ S(\triangleright) = \sum_{1 \le j \le k \le n} a_j a_k \]

The array is symmetrical about its main diagonal, meaning the value at row \( j \) and column \( k \) is identical to the value at row \( k \) and column \( j \) where \( a_j a_k = a_k a_j \).

2 Symmetry and Partitioning

The main diagonal consists of elements where the row index equals the column index (\( j=k \)). Due to symmetry, the upper triangle \( S(\triangleleft) \) is identical to the lower triangle \( S(\triangleright) \). Consequently:

\[ S(\triangleright) = \sum_{1 \le j \le k \le n} a_j a_k = \sum_{1 \le k \le j \le n} a_k a_j = S(\triangleleft) \]

Using Iverson's convention, we can observe the relationship between the sets of indices:

\[ [1 \le j \le k \le n] + [1 \le k \le j \le n] = [1 \le j, k \le n] + [1 \le j = k \le n] \]

3 Set Combinations

Applying the laws of summation over sets \( K \) and \( K' \), the sum over the union plus the sum over the intersection equals the sum of the individual sets:

\[ \sum_{z \in K} f(z) + \sum_{z \in K'} f(z) = \sum_{z \in K \cap K'} f(z) + \sum_{z \in K \cup K'} f(z) \]

\( K \): Lower Triangle \( S(\triangleright) \)

\( K' \): Upper Triangle \( S(\triangleleft) \)

\( K \cap K' \): Main Diagonal \( (j=k) \)

\( K \cup K' \): Entire Grid \( (1 \le j, k \le n) \)

4 Final Derivation

The sum over the entire grid factors into the square of the total sum:

\[ \sum_{1 \le j, k \le n} a_j a_k = \left( \sum_{k=1}^n a_k \right)^2 \]

Substituting our known values into the set identity and utilizing the equality of the triangles:

\[ S(\triangleright) = \frac{1}{2} \left( \left( \sum_{k=1}^n a_k \right)^2 + \sum_{k=1}^n a_k^2 \right) \]