2
$\begingroup$

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?

  • 1
    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.2012-01-21

1 Answers 1

2

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]$.

  • 0
    Thank you, I now understand that he wanted to sum the diagonal row twice. I forgot to put the final step, but it involves adding S to itself, then after simplifying the RHS divide by two and have an expression for the upper trianglar sum.2012-01-21