1

I encounter following problem i have triple summation where limit of inner summation depends on indexes of previous two summation (which commutes) $\sum_{i=0}^a\sum_{j=0}^b\sum_{k=0}^{j+i}$ and a desired form is to change order of summations to move summation over k outward. I started to doing it graphically as for example here https://www.youtube.com/watch?v=9QJt03983Gg and i was able to split it into $\frac{1}{4}(\sum_{k=0}^a\sum_{j=0}^b\sum_{j=k}^{a}+\sum_{k=0}^b\sum_{j=k}^b\sum_{i=0}^{a}+\sum_{i=0}^a\sum_{j=0}^b\sum_{k=j+1}^{j+i}+\sum_{i=0}^a\sum_{j=0}^b\sum_{k=i+1}^{j+i})$. And still i have a trouble at this point to exchange order in two last reaming summations. Any advice how to go with that further? Thanks in advance for any help

Tupta
  • 13
  • 2

1 Answers1

0

For a sum such as this, a graphical approach to exchanging the order might not be the best, but it is not too bad using just inequalities.

We can first exchange the order of the sum over $j$ and the sum over $k$, with $i$ fixed. $$\sum_{j=0}^b\sum_{k=0}^{i+j}$$ When changing the order of summation, it can be helpful to write out everything we know about the indices: \begin{align*} 0&\leq j \leq b, \\0&\leq k \leq i+j\leq i+b. \end{align*} We want the sum over $k$ to be on the outside, so we take the maximum range of values taken by $k$, that is $0\leq k\leq i+b$. We can also rearrange the above inequalities to get restrictions on $j$ \begin{align*} 0&\leq j \leq b, \\k-i &\leq j\leq b. \end{align*} For both of these to be true, we must have $\max(0,k-i)\leq j \leq b$, and so the sum becomes $$\sum_{i=0}^a\sum_{k=0}^{i+b}\sum_{j=\max(0,k-i)}^b.$$

Next, we can exchange the order of the sum over $i$ and the sum over $k$. $$\sum_{i=0}^a\sum_{k=0}^{i+b}$$ Again, writing out everything we know: \begin{align*} 0&\leq i \leq a, \\0&\leq k \leq i+b\leq a+b. \end{align*} As before, we want the sum over $k$ to be on the outside, so we take the maximum range of values taken by $k$, that is $0\leq k\leq a+b$. We can also rearrange the above inequalities to get restrictions on $i$ \begin{align*} 0&\leq i \leq a, \\k-b &\leq i\leq a. \end{align*} So $\max(0,k-b)\leq i \leq a$ and the reordered sum is $$\sum_{k=0}^{a+b}\sum_{i=\max(0,k-b)}^a\sum_{j=\max(0,k-i)}^b$$

Freddie
  • 326