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?

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ – Davide Giraudo Jan 21 '12 at 11:01
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – Ammar Alammar Jan 21 '12 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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