How to change the order of summation?

Question

I have stumbled upon, multiple times, on cases where I need to change the order of summation (usally of finite sums).

One problem I saw was simple $$ \sum_{i=1}^{\infty}\sum_{j=i}^{\infty}f(i,j)=\sum_{j=1}^{\infty}\sum_{i=1}^{j}f(i,j) $$

and I can go from the first sum to the second by noting that the constraints are $$ 1\leq i\leq j<\infty $$ so the first double sum does not constrain on $i$ and constrains $j$ to $j\geq i$. The second double summation doesn't put any constrains on $j$ but constrains $i$ relative to $j$ $(1\leq i\leq j)$.

While this approach works for simple examples such as this. I am having problems using it where the bounds are more complicated.

The current problem interchanges the following $$ \sum_{i=1}^{n-1}\sum_{k=2}^{n-i+1}\to\sum_{k=2}^{n}\sum_{i=1}^{n+1-k} $$

I started by writing $$ k\leq n-i+1 $$

and got $$ i\leq n-k+1 $$

but all other bounds are not clear to me..

the problem is that I can't use this technique since I can't write the inequalities in the same form of $$ 1\leq i\leq f(j)\leq n $$

where $n$ is some bound (possibly $\infty$).

My question is how to approach the second example by a technique that should be able to handle similar cases

Answer 1

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.

Answer 2

You can look at it this way: you're looking to sum all the following terms:

$$\begin{matrix} &i&1&2&3&4&\cdots&n-2&n-1\\ k\\ 2&&(1,2)&(2,2)&\cdots&\cdots&\cdots&(n-2,2)&(n-1,2)\\ 3&&(1,3)&(2,3)&\cdots&\cdots&\cdots&(n-2,3)\\ 4&&(1,4)&(2,4)\\ 5&&(1,5)&(2,5)\\ \vdots&&\vdots&\vdots&\\\ &&\vdots&(2,n-1)\\ n&&(1,n) \end{matrix}$$

The first way you wrote it corresponds to summing the terms column by column, then adding those sums up. To turn it into the second form, you'll have to add the terms of each row then add them all up. The bound on $i$ becomes $1\leq i \leq n- k+1$ as for $k$: $2\leq k\leq n$.

Also, as you wrote, we have $2\leq k\leq n-i+1$, the maximum value for $k$ is reached when $i=1$, so $2\leq k\leq n$. As for the bounds on $i$ you have already found them!

Answer 3

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).

Answer 4

The double sum implements the contraints

$$1\le i\le n-1,\\2\le k\le n-i+1.$$

Substituting the extreme values of $i$, you obtain the possible extreme values of $k$

$$2\le k\le \max(n-1+1,n-(n-1)+1)$$ or

$$2\le k\le n.$$

Then if you fix $k$ and express $i$ in terms of it, you get the constraint

$$i\le n-k+1,$$ which you combine with the range

$$1\le i\le\min(n-k+1,n-1)=n-k+1.$$

So

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

---

Similarly in the first case,

$$1\le i,\\i\le j.$$

The range of $j$ is $1\le j$, and with $j$ fixed, $1\le i\le j$, giving

$$\sum_{j=1}^\infty\sum_{i=j}^\infty.$$