I'm sorry if this question is too novice, but I am just beginning discrete math. I've been working through the book Concrete Mathematics (Graham,Knuth,Patashnik) and I reached a double summation that has me very confused. I'v been trying to work it out, and I think I have a solution but I'm not sure if it is the correct way to solve it.

The question comes from chapter 2 section 4 and it goes as follows: \begin{equation} S = \displaystyle\sum\limits_{1 \le j < k \le n}^{}{(a_k - a_j)(b_k - b_j)} \end{equation}

The authors then go on to say " We have symmetry when j and k are interchanged:" and write the new sum: \begin{equation} S = \displaystyle\sum\limits_{1 \le k < j \le n}^{}{(a_j - a_k)(b_j - b_k)} = \displaystyle\sum\limits_{1 \le k < j \le n}^{}{(a_k - a_j)(b_k - b_j)} \end{equation} I understand how they can get to the 2nd sum, because all you're doing is changing index names. But how do the authors get from the 2nd sum to the 3rd sum? Or how do they use their previously mentioned "Rocky Road" formula to achieve this result?


EDIT: Sorry for not making the Rocky Road formula clear. The Rocky Road Formula is as follows:

\begin{equation} \displaystyle\sum\limits_{j \in J}^{}{\displaystyle\sum\limits_{k \in K(j)}^{}{a_j,_k}} = \displaystyle\sum\limits_{k \in K'}^{}{\displaystyle\sum\limits_{j \in J'(k)}^{}{a_j,_k}} \end{equation}


All we're doing in moving from the second sum to the third sum is essentially multiplying each bracket by $-1$, but since there are two brackets, the two factors of $-1$ cancel out so the sum is unchanged.

  • $\begingroup$ I see.Thanks for the pointing that out! The one thing I still don't get is their application of Rocky Road into this sum $\endgroup$ – Alejandro Jun 7 '13 at 15:38
  • $\begingroup$ Sorry, I'm not familiar with the phrase Rocky Road in this context. If you give a brief description of it though I can probably answer that for you. $\endgroup$ – john Jun 7 '13 at 15:40
  • 1
    $\begingroup$ Thanks. I'll add the Rocky Road to the question since It requires latex formatting $\endgroup$ – Alejandro Jun 7 '13 at 15:42
  • $\begingroup$ I added the Rocky Road formula to the original question $\endgroup$ – Alejandro Jun 7 '13 at 15:46
  • 1
    $\begingroup$ If I understand what you mean by that formula (particularly by J, K, etc.) then I would say they haven't applied the formula at all yet. All they've done so far is interchange dummy variables and do some basic algebra inside the summation. There hasn't actually been any re-expressing of the sum per se though. $\endgroup$ – john Jun 7 '13 at 15:51

In this book author say with Iversonian notation if $$P(j,k)=[j \in J][k \in K(j)]= [k \in K^{'}][j \in J^{'}(k)]$$ then we can use any of this statements for index of sum. for example $$P(j,k)= [1 \leqslant‎ j \leqslant‎ k \leqslant‎ n]=[1 \leqslant‎ j \leqslant‎ n][j \leqslant‎ k \leqslant‎ n] =[1 \leqslant‎ k \leqslant‎ n][1 \leqslant‎ j \leqslant‎ k] $$ then the summation with single index $$1 \leqslant‎ j \leqslant‎ k \leqslant‎ n $$ is equal to double summations with two other perdicates.


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.