3
$\begingroup$

Sorry for asking a very dumb question, but in Concrete Mathematics(Graham,Knuth,Patashnik), chapter 2 section 4, Knuth talks about this formula called "Rocky Road".

This is the formula to use when you want to interchange the order of summation of a double sum whose inner sum's range depends on the index variable of the outer sum, like this:

\begin{equation} \displaystyle\sum\limits_{j = 1}^{n}{\displaystyle\sum\limits_{k = j}^{n}{a_j,_k}} \end{equation}

The rocky road formula is as follows: \begin{equation} \displaystyle\sum\limits_{j \in J}^{}{\displaystyle\sum\limits_{k \in K(j)}} = \displaystyle\sum\limits_{k \in K'}{\displaystyle\sum\limits_{j \in J'(k)}} \end{equation}

With the requirement that the sets $J,K(j),K', \text{and} J'(k)$ be related in such a way that: \begin{equation} [j \in J][k \in K(j)] = [k \in K'][j \in J'(k)] \end{equation}

My understanding of this, is that the set $K'$ is basically the "bounds" that $k$ has, sort of like its restrictions. For the first sum I wrote, I would think that K' be the set {j,j+1,...,n} and since j starts at 1, K' is really just the set of the values $1 \rightarrow n$. However, I can't really figure out $J'(k)$ here , or even if my understanding of $K'$ is right. Can anyone give me some pointers or put me in the right track as to understanding this set relation?

Thanks,

$\endgroup$
  • $\begingroup$ Yeah sorry, fixed it already. I just know that most people simply reference it as (Knuth). $\endgroup$ – Alejandro Jun 10 '13 at 0:41
2
$\begingroup$

The requirement is basically saying that you must sum over the same set of numbers $a_{j,k}$ on both sides: if a particular pair $(j, k)$ occurs somewhere on the left-hand side, then $(k, j)$ must occur somewhere on the right-hand side, and vice-versa.

Looking at some simple examples might help.


$$\sum_{j=1}^{n} \sum_{k=1}^{n} a_{j,k} = \sum_{k=1}^{n} \sum_{j=1}^{n} a_{j,k}$$

It should be clear to you that the above equation holds: Here, you're summing over all numbers $a_{j,k}$ such that $1 \le j \le n$ and $1 \le k \le n$. In terms of the notation, $J = \{1, 2, \dots, n\}$, $K(j) = \{1, 2, \dots, n\}$, $K' = \{1, 2, \dots, n\}$, and $J'(k) = \{1, 2, \dots, n\}$ (all the same).


$$\sum_{j=1}^{n} \sum_{k=j}^{n} a_{j,k} = \sum_{k=1}^{n} \sum_{j=1}^{k} a_{j,k}$$

Here, if you view the numbers $a_{j,k}$ as being laid out in an $n \times n$ matrix, then on the left hand side, you're summing over the "upper triangle" (numbers on or above the diagonal) of the matrix: for each row ($j$), you add up numbers from only those columns ($k$) that occur at $j$ (on the diagonal) or more (to the right). If you try to describe this "upper triangle" write it by columns instead, then for each column $k$, you must add up the numbers from the rows $j$ that either occur on the diagonal (so, at $k$) or above it (so, smaller $j'$). That gives the right-hand side.

How the notation helps here (or may help) is that you can say $[j \in J] = [1\le j \le n]$, and $[k \in K(j)] = [j\le k \le n]$, so after taking $K' = \{1, 2, \dots, n\}$ so that $[k \in K'] = [1 \le k \le n]$, you're trying to find $J'(k)$ such that $$\begin{align} [k \in K'][j \in J'(k)] &= [j \in J][k \in K(j)] \\ [1 \le k \le n][j \in J'(k)] &= [1 \le j \le n][j \le k \le n] = [1 \le j \le k \le n]\\ \end{align}$$ which says you must take $[j \in J'(k)] = [1 \le j \le k]$ or $J'(k) = \{1, 2, \dots, k\}$. Thus the sum on the right-hand side.

Whether the notation helps you more than thinking directly, varies from person to person and depends on you.


A final example, slightly less trivial, which you can work out for yourself:

$$\sum_{j=1}^{n} \sum_{k\text{ divides }j} a_{j, k} = \sum_{k=1}^{n} \sum_{\substack{j\text{ is a multiple of }k\\\text{and }j \le n}} a_{j, k}$$

$\endgroup$
  • $\begingroup$ Wow! Thanks for such an excellent answer! I really understand it now :) So basically, K' is, in essence, all the values of k(j)? $\endgroup$ – Alejandro Jun 10 '13 at 2:50
  • $\begingroup$ @user1274223: If any value $k$ occurs on the left-hand side (for some $j$), then it must also occur on the right-hand side (where it does not depend on $j$), and therefore yes, it must be in the set $K'$. (But as a technicality, note that in principle you can, if you wish, make $K'$ even larger (put values of $k$ in it that don't occur in any $K(j)$ on the left-hand side) as long as for those "extra" $k$, the corresponding sets $J'(k)$ are empty sets, so that those "extra" $k$" don't actually contribute any values to the right-hand side of the sum.) $\endgroup$ – ShreevatsaR Jun 10 '13 at 3:05
  • $\begingroup$ I completely get it now! Thanks so much! $\endgroup$ – Alejandro Jun 10 '13 at 9:52
1
$\begingroup$

I like that book a lot, but I think this is being made more complicated than it really is.

I think it easier to write the sum symmetrically as $ \sum\limits_{(j,k) \in S} $ where $ S = \{ (j,k) | j \in J, k \in J(k) \} $. Then you can think of $ S \subset \mathbb{Z}^2 $, and exchanging the order of the sum corresponds to slicing horizontally rather than vertically. That is, $ J'(k) $ is the horizontal slice of $ S $ at y-coordinate $ k $. So as you correctly point out $ K' = \pi_2 S$, the projection to second coordinate. (Actually, all you really need is $ \pi_2 S \subset K' $, since if $ J'(k) $ is empty. you won't sum over that k.)

For your example, $ S = \{ (j,k) | \; 1 \leq j \leq n, \; 1 \leq \ k \leq n, \; j \leq k \} $. From this read immediately that $ J'(k) = \{ j | \; 1 \leq j \leq n, \; j \leq k \} $.

$\endgroup$
  • $\begingroup$ Thank you for your answer! But could you please explain what you mean by writing the sum symmetrically and slicing horizontally vs vertically? $\endgroup$ – Alejandro Jun 10 '13 at 2:29
  • $\begingroup$ +1 (Ignore my earlier comment; hadn't read this answer carefully the first time.) $\endgroup$ – ShreevatsaR Jun 10 '13 at 2:34

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.