## 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 i 1 2 3 1 11 12 13 2 22 23 3 33