# Sum of $n^2$ array of $a_ja_k$

I'm trying to learn about sums from the book Concrete Mathematics which gives this problem:

We have the array

$$\begin{bmatrix} a_1a_1 & a_1a_2 & \ldots & a_1a_n\\ a_2a_1 & a_2a_2 & \ldots & a_2a_n\\ \vdots & \vdots & \ddots & \vdots\\ a_na_1 & a_na_2 & \ldots & a_na_n \end{bmatrix}$$ of $n^2$ products of $a_ja_k$. And we want to find a simple formula for

$$S_◹ = \sum_{1 \leq j \leq k \leq n} a_ja_k$$ which is approximately half the the sum of all the elements. Then he manipulate the equation as such:

$$S_◹ = \sum_{1 \leq j \leq k \leq n} a_ja_k = \sum_{1 \leq k \leq j \leq n} a_ka_j = \sum_{1 \leq k \leq j \leq n} a_ja_k = S_◺$$

So far so good, but then he manipulates the indices as such:

$$\label{1} [ 1 \leq j \leq k \leq n] + [1 \leq k \leq j \leq n] = [1 \leq j,k \leq n] + [1 \leq j=k \leq n]$$

As far as I can tell from the introduction of the $j,k$ notation it means the permutations over all integers $j$ and $k$. But when I try his manipulation to the indices for small value of $n$ I see that it counts the diagonal twice, so we should subtract the $[1 \leq j=k \leq n]$ instead of adding it. Can someone explain why he used addition?

-
In the LHS we summed two times over the diagonal elements, and if we take the sum over $[1\leq j,k\leq n]$ we sum them only one time. So we have to correct this, adding one time the diagonal elements. –  Davide Giraudo Jan 21 '12 at 11:01

We can write, using your notations \begin{align*}[1\leq j\leq k\leq n]+[1\leq k\leq j\leq n]&=[1\leq j< k\leq n]+[1\leq j=k\leq n]\\ &+[1\leq k< j\leq n]+[1\leq k=j\leq n]\\ &=[1\leq j,k\leq n]+[1\leq k=j\leq n], \end{align*} since the first three terms of the RHS of the first equality are exactly $[1\leq j,k\leq n]$.