Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 2 down vote accepted

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

share|cite|improve this answer
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. – Ammar Alammar Jan 21 '12 at 16:35

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.