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

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 2

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.

Answer 3

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 4

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 5

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