Double Summation Trick

Question

I have seen a couple of times the trick where $\displaystyle\sum_{i=1}^\infty \sum_{j=i}^\infty f(j)$ becomes $\displaystyle\sum_{j=1}^\infty \sum_{i=1}^j f(j)$ How does this work? I am so confused. Is there also a more general trick when you don't have $\infty$ or only one of them is $\infty$ or even when it's not just a function of $j$? e.g

$\displaystyle\sum_{i=1}^m \sum_{j=i}^n f(i,j)$ ?

Answer 1

In the diagram, I let $(i=a,j=b)$ represent an ordered pair $(a,b)$ in a table that goes to infinity. A square $(a,b)$ that a segment or ray touches means the summation includes that term, $f(a,b)$. The idea behind rewriting the sum is to add ("hit" with a segment or ray) exactly the same terms in a different way.

In the first table, the rays from left to right (going to infinity) represent

$$\sum\limits_{j=1}^{\infty}f(1,j)+\sum\limits_{j=2}^{\infty}f(2,j)+\sum\limits_{j=3}^{\infty}f(3,j)+\dots=\sum\limits_{i=1}^{\infty}\left(\sum\limits_{j=i}^{\infty}f(i,j)\right)$$

In the second table, the segments from top to bottom (going to infinity) represent

$$\sum\limits_{i=1}^{1}f(i,1)+\sum\limits_{i=1}^{2}f(i,2)+\sum\limits_{i=1}^{3}f(i,3)+\dots=\sum\limits_{j=1}^{\infty}\left(\sum\limits_{i=1}^{j}f(i,j)\right)$$

Your extension for finite bounds is similar, which will be clear by drawing a similar $n\times m$ table and looking at what is being added.

When $m=n$, it's straightforward to cut off terms from the infinite sum and change bounds accordingly:

$$\sum\limits_{i=1}^m\sum\limits_{j=i}^nf(i,j)=\sum\limits_{j=1}^{m}\sum\limits_{i=1}^{j}f(i,j)$$

When $m<n$, some rows in the second diagram will be "filled out across," possibly infinitely many if $n=\infty$:

$$\sum\limits_{i=1}^m\sum\limits_{j=i}^nf(i,j)=\sum\limits_{j=1}^{m}\sum\limits_{i=1}^{j}f(i,j)+\sum\limits_{j=m}^{n}\sum\limits_{i=1}^{m}f(i,j)$$

Also note this only makes sense when $m\leq n$ (if $m>n$, it doesn't make sense on the left side to have e.g. $i=n+1$ and then have to sum from $j=i=n+1$ "up to" $n$, and similarly on the right for $j=m$ up to $n$). To make sense of the $m>n$ case, we could just let both bounds equal $\min(m,n)$ and fall back to the $m=n$ case.

Answer 2

In the case where the upper limit is not infinite and are equal, the sum can be restated as follows:

$$\sum_{i=1}^n\sum_{j=i}^n f(i,j)=\sum_{1\le i\le j\le n}f(i,j)=\sum_{j=1}^n\sum_{i=1}^j f(i,j)$$

From the inequality in the range it is clear that whilst each of $i, j$ can run from $1$ to $n$, $j$ cannot be less than $i$ (the initial form) which is the same as saying that $i$ cannot be more than $j$ (the final form).