A Simple but Handy Formula for Reversing ‘Triangular’ Sums

Sometimes it is useful to swap the order of the summations in a double summation. This isn’t completely obvious when the limits of one sum are dependent on another. Here’s the formula:

\sum_{i=h}^{k} \sum_{j=i}^{k} \varphi(i,j) = \sum_{j=h}^{k} \sum_{i=h}^{j} \varphi(i,j)

Note that inside the sum, we always have h \le i \le j \le k. On the left, i runs from h to k, and j runs from i to k (i.e. h \le i \le k and i \le j \le k). On the right, i runs from h to j, and j runs from h to k (i.e. h \le i \le j and h \le j \le k). Those are all summarised by h \le i \le j \le k.

A particularly common case is h=0 and k=n:

\sum_{i=0}^{n} \sum_{j=i}^{n} \varphi(i,j) = \sum_{j=0}^{n} \sum_{i=0}^{j} \varphi(i,j)

Notice here that within the sum 0 \le i \le j \le n.

Another common one is h=1 and k=n:

\sum_{i=1}^{n} \sum_{j=i}^{n} \varphi(i,j) = \sum_{j=1}^{n} \sum_{i=1}^{j} \varphi(i,j)

Notice in this case that within the sum 1 \le i \le j \le n.

To really illustrate this, let’s take the following simple example: h=1 and k=3 with \varphi(i,j) = i^j. It doesn’t matter what φ is; I’ve only chosen this for compactness of example. First, let’s expand the left:

\sum_{i=1}^{3} \sum_{j=i}^{3} i^j

= \sum_{j=1}^{3} 1^j + \sum_{j=2}^{3} 2^j + \sum_{j=3}^{3} 3^j

= (1^1 + 1^2 + 1^3) + (2^2 + 2^3) + (3^3)

Now the right:

\sum_{j=1}^{3} \sum_{i=1}^{j} i^j

= \sum_{i=1}^{1} i^1 + \sum_{i=1}^{2} i^2 + \sum_{i=1}^{3} i^3

= (1^1) + (1^2 + 2^2) + (1^3 + 2^3 + 3^3).

All that’s changed is the order.

I used the term ‘triangular sum’ in the title because of this:

j
1 2 3
i 1 11 12 13
2 22 23
3 33
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: