How to change the order of summation?

Solution 1:

Changing the order in the first double sum is manageable. We could therefore use it as some kind of prototype. We transform the second double sum, so that the index range is similar to the first one.

first double sum:

The following presentation of the index range might be helpful. \begin{align*} \sum_{i=1}^{\infty}\sum_{j=i}^{\infty}f(i,j)=\sum_{\color{blue}{1\leq i\leq j<\infty}}f(i,j)=\sum_{j=1}^{\infty}\sum_{i=1}^{j}f(i,j) \end{align*} If we focus on the middle double sum and look at the index range $1\leq i\leq j<\infty$ we observe the left-hand side as well as the right-hand side can be easily derived.

We do some rearrangements to derive a similar representation in the

second double sum:

We obtain \begin{align*} \sum_{i=1}^{n-1}\sum_{k=2}^{n-i+1}g(i,k)&=\sum_{i=1}^{n-1}\sum_{k=2}^{i+1}g(n-i,k)\tag{1}\\ &=\sum_{i=1}^{n-1}\sum_{k=1}^{i}g(n-i,k+1)\tag{2}\\ &=\sum_{1\leq k\leq i\leq n-1}g(n-i,k+1)\tag{3}\\ &=\sum_{k=1}^{n-1}\sum_{i=k}^{n-1}g(n-i,k+1)\tag{4} \end{align*}

Comment:

• In (1) we change the order of the first sum $i\rightarrow n-i$. Note, that reversing the order this way \begin{align*} \sum_{i=1}^{n-1}a(i)&=a(1)+a(2)+\cdots+a(n-1)\\ &=a(n-1)+a(n-2)+\cdots+a(1)\\ &=\sum_{i=1}^{n-1}a(n-i) \end{align*} does not change the lower and upper index of $i$, but each occurrence of $i$ within the sum has to be substituted with $n-i$. So, we replace $a(i)$ with $a(n-i)$.

• In (2) we shift the index $k$ by one, so that we also can start with $k=1$.

• In (3) we write the double sum as we did in the first case.

• In (4) it's easy to change the order of the double sum based upon the representation in (3).

Solution 2:

I solve this kind of problem with the following steps:

1. Draw a plane i-k (in general is over your dummy index, remember this index can be called as you want). You'll find the conditions over the sum generates a triangle, in this case.
2. The last step is to try to generate the last graphic changing the order of the sum,i.e., if your first sum is over i, now this index will be the last, so your first sum is over k in this case when you change the order.

Well with this steps you'll find the same answer you put in the description. I couldn't do it at this moment with graphics to show you, I encourage you to try it uniquely following this steps.

Solution 3:

I've found the Iverson bracket extremely useful for this sort of calculation. For a reference on the technique, I learned it from Concrete Mathematics

The Iverson bracket is a function whose argument is a proposition, and is defined by the formula

$$ [P] = \begin{cases} 0 & P \text{ is false} \\ 1 & P \text{ is true} \end{cases} $$

You use this to express summations, such as

$$ \sum_{n=a}^b f(n) = \sum_{n \in \mathbb{Z}} [a \leq n \leq b] f(n) $$

When using this technique, you generally take all sums to be over all integers and use the Iverson brackets to control which terms are actually summed over. I will henceforth suppress the $\in \mathbb{Z}$.

It's additionally useful to use the convention that when $P$ is false, that $[P]$ is strongly zero; that is, when P is false, we always say $[P] t = 0$ no matter what $t$ is, even when $t$ is undefined. As an example of this usage:

$$ \frac{\pi^2}{6} = \sum_{n} [n \geq 1] \frac{1}{n^2} $$

Normally we would say the right hand side is undefined, since $\frac{1}{n^2}$ is undefined when $n=0$. But by the "strongly zero" convention, we say that $[n \geq 1] \frac{1}{n^2}$ is well-defined and zero when $n=0$, so this sum makes sense.

Now, to apply it to your example:

$$\sum_{i=1}^{n-1}\sum_{k=2}^{n-i+1}\to\sum_{k=2}^{n}\sum_{i=1}^{n+1-k}$$

$$\sum_{i=1}^{n-1}\sum_{k=2}^{n-i+1} = \sum_{i,k} [1 \leq i \leq n-1] [2 \leq k \leq n-i+1] $$

Note that $[P][Q] = [P \text{ and } Q]$. Multiplication is somewhat more convenient notation, though, so I leave it expressed as a product.

One could approach this problem by finding a different way of expressing this system of inequalities. We can rewrite them as

$$ 1 \leq i \qquad i \leq n-1 \qquad \qquad 2 \leq k \qquad \qquad i \leq n+1-k $$

The $i \leq n-1$ condition is redundant. Having "solved" the last inequality for $i$ it's clear that we can rewrite

$$ [1 \leq i \leq n-1] [2 \leq k \leq n-i+1] = [2 \leq k] [1 \leq i \leq n+1-k] $$

Depending on our purposes, it may help to observe the implicit $1 \leq n+1-k$ constraint and solve it for $k$ to make it more explicit, so we have

$$ \ldots = [2 \leq k \leq n] [1 \leq i \leq n+1-k] $$

It's clear now that

$$ \sum_{i,k} [2 \leq k \leq n] [1 \leq i \leq n+1-k] = \sum_{k=2}^n \sum_{i=1}^{n+1-k} $$

if we really want to rewrite the summation back into this form.

One way in which this notation becomes really useful, in my opinion, when you consider changing variables. If I was given

$$ \sum_{i,k} [1 \leq i \leq n-1] [2 \leq k \leq n-i+1] $$

I would often consider simplifying the upper bound by making a substitution $j = n-i+1$ (or $i = n-j+1$), replacing the sum over $i$ with a sum over $j$

$$ \ldots = \sum_{j,k} [1 \leq n-j+1 \leq n-1] [2 \leq k \leq j] \\= \sum_{j,k} [1 \leq n-j+1] [n-j+1 \leq n-1] [2 \leq k \leq j] \\= \sum_{j,k} [j \leq n] [2 \leq j] [2 \leq k \leq j] \\= \sum_{j,k} [2 \leq k \leq j \leq n] $$

which makes it easy to see other ways to rewrite this. E.g. if I wanted to sum over $k$ first, it's clear this becomes

$$ \ldots = \sum_{j,k} [2 \leq k \leq n] [k \leq j \leq n] \\= \sum_{k=2}^n \sum_{j=k}^n $$

Or I could change $j$ back to $i$ first if I wanted.