Vtyjkyuk

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^inftysum_j=i^inftyf(i,j)=sum_j=1^inftysum_i=1^jf(i,j)
$$

and I can go from the first sum to the second by noting that the
constraints are
$$
1leq ileq j<infty
$$
so the first double sum does not constrain on $i$ and constrains
$j$ to $jgeq i$. The second double summation doesn't put any constrains
on $j$ but constrains $i$ relative to $j$ $(1leq ileq 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-1sum_k=2^n-i+1tosum_k=2^nsum_i=1^n+1-k
$$

I started by writing
$$
kleq n-i+1
$$

and got
$$
ileq 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
$$
1leq ileq 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

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.
beginalign*
sum_i=1^inftysum_j=i^inftyf(i,j)=sum_colorblue1leq ileq j<inftyf(i,j)=sum_j=1^inftysum_i=1^jf(i,j)
endalign*
If we focus at the middle double sum and look at the index range $1leq ileq 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
beginalign*
sum_i=1^n-1sum_k=2^n-i+1g(i,k)&=sum_i=1^n-1sum_k=2^i+1g(n-i,k)tag1\
&=sum_i=1^n-1sum_k=1^ig(n-i,k+1)tag2\
&=sum_1leq kleq ileq n-1g(n-i,k+1)tag3\
&=sum_k=1^n-1sum_i=k^n-1g(n-i,k+1)tag4
endalign*

Comment:

• In (1) we change the order of the first sum $irightarrow n-i$. Note, that reversing the order this way
  beginalign*
  sum_i=1^n-1a(i)&=a(1)+a(2)+cdots+a(n-1)\
  &=a(n-1)+a(n-2)+cdots+a(1)\
  &=sum_i=1^n-1a(n-i)
  endalign*
  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).

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.

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

$$beginmatrix
&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)
endmatrix$$

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 $1leq i leq n- k+1$ as for $k$: $2leq kleq n$.

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

The double sum implements the contraints

$$1le ile n-1,\2le kle n-i+1.$$

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

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

$$2le kle n.$$

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

$$ile n-k+1,$$ which you combine with the range

$$1le ilemin(n-k+1,n-1)=n-k+1.$$

So

$$sum_k=2^nsum_i=1^n-k+1$$

Similarly in the first case,

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

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

$$sum_j=1^inftysum_i=j^infty.$$

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] = begincases 0 & P text is false \ 1 & P text is true endcases $$

You use this to express summations, such as

$$ sum_n=a^b f(n) = sum_n in mathbbZ [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 mathbbZ$.

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:

$$ fracpi^26 = sum_n [n geq 1] frac1n^2 $$

Normally we would say the right hand side is undefined, since $frac1n^2$ is undefined when $n=0$. But by the "strongly zero" convention, we say that $[n geq 1] frac1n^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-1sum_k=2^n-i+1tosum_k=2^nsum_i=1^n+1-k$$

$$sum_i=1^n-1sum_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.