# How do I start this summation (double series?)

I'm unfamiliar with this type of problem, but I've been asked to write out the result of n = 8.

The problem: Prove that

$$\sum_{i = 1}^{n} \sum_{j = 1}^{i} f(i, j) = \sum_{j = 1}^{n} \sum_{i = j}^{n} f(i, j)$$

To start it off, I've just been asked to do the first 8 iterations, but I'm honestly not sure what it would look like.

If I do the left side of the equal sign, my guess is the results would look something like

$$f(1,1) + f(2, 2) ...$$

but that doesn't seem right at all. Can someone explain what I should be doing, or perhaps show me how the first few iterations will look like so I can work on the problem?

-

The sum on the left is $$f(1,1)+f(2,1)+f(2,2)+f(3,1)+f(3,2)+f(3,3)+f(4,1)+f(4,2)+f(4,3)+f(4,4)+f(5,1)+\cdots+f(n,n-1)+f(n,n).$$ Regarding how to switch the indices when you flip the sums, I usually think about it this way: I write, for the sum in the left, $$1\leq i\leq n, \ 1\leq j\leq i.$$ Now that you want to flip the indices, you need to start with $j$ outside. As $j$ takes eventually every value up to $n$, we have $1\leq j\leq n$. But if you look at the second inequality above, $i\geq j$ always, and it is $n$ at most. So $$1\leq j\leq n, \ \ j\leq i\leq n.$$

-
Thank you, this really shed some light on it. I was unfamiliar with a double summation so I had no clue how I should work with it. Seeing the example you provided helped as well as the indices explanation. – ConfusingCalc Sep 26 '13 at 18:57

You need to show that if we let $A = \{ (i,j) | 1\le i \le n, \ 1 \le j \le i \}$ and $B = \{ (i,j) | 1\le j \le n, \ j \le i \le n \}$, then $A=B$. That is, the collection of indices are the same. Order does not matter here.

Suppose $(i,j) \in A$. Then $1\le i \le n, \ 1 \le j \le i$. Hence $1 \le j \le i \le n$ and $j \le i \le n$, hence $(i,j) \in B$. So $A \subset B$.

Suppose $(i,j) \in B$. Then $1\le j \le n, \ j \le i \le n$. Hence $1\le i \le n$ and $1 \le j \le i$, hence $(i,j) \in A$. So $B \subset A$, and we are finished.

We can just write the summation as $\sum_{(i,j) \in A} f(i,j)$.

-
Thank you for this, this will be a big help when I get to the proof part! I really appreciate it – ConfusingCalc Sep 26 '13 at 19:05

For $n = 2$, the left-hand side would expand to:

$$\sum_{j=1}^1 + \sum_{j=1}^2 = f(1,1) + \left[ f(2,1) + f(2,2) \right]$$

And the right hand side:

$$\sum_{i=1}^2 + \sum_{i=2}^2 = \left[ f(1,1) + f(2,1) \right] + f(2,2)$$

-
Thanks for the example, this is exactly the type of response I was looking for. – ConfusingCalc Sep 26 '13 at 19:03

$\sum_{i = 1}^{n} \sum_{j = 1}^{i} f(i, j) ,n=8$

$f(1,1)+(f(2,1)+f(2,2))+(f(3,1)+f(3,2)+f(3,3))+(f(4,1)+f(4,2)+f(4,3)+f(4,4))+..$

$\sum_{j = 1}^{n} \sum_{i = j}^{n} f(i, j),n=8$

$(f(1,1)+f(2,1)+f(3,1)+f(4,1)+f(5,1)+f(6,1)+f(7,1)+f(8,1))+ (f(2,2)+f(3,2)+f(4,2)+f(5,2)+f(6,2)+f(7,2))+f(8,2))+(f(3,3)+f(4,3)....)...$

I hope you see how both are the same just in a different order

-
Thank you for posting this, it will help for when I have to write my proof for it! It looks like it works very similar to a while/for loop in programming. – ConfusingCalc Sep 26 '13 at 18:58

Hint: Show $$\sum_{i = 1}^{n} \sum_{j = 1}^{i} f(i, j) = \sum_{1\le j \le i \le n} f(i,j) = \sum_{j = 1}^{n} \sum_{i = j}^{n} f(i, j)$$

-
Thank you for the hint, it is much appreciated. I think the hint you gave is geared more toward solving the proof (which is what I'll need to do next)! In this question I was simply looking at how to expand the summation correctly. Proving it will likely be much more work. I'll check back on this hint when I get to the proof part. – ConfusingCalc Sep 26 '13 at 19:04

One can always make a drawing. Consider the $ij$-plane. The first sum $$\sum_{i=1}^n\sum_{j=1}^i=\sum_{1\leqslant i\leqslant n}\sum_{1\leqslant j\leqslant i}$$ lets $i$ range freely, but asks that $j\leqslant i$ (everything under the line $i=j$, looking from the $i$ axis). The other sum $$\sum_{j=1}^n\sum_{j=1}^i=\sum_{1\leqslant i\leqslant n}\sum_{j\leqslant i\leqslant n}$$ lets $j$ range freely, but asks $i\geqslant j$ (everything over the line $j=i$, looking from the $j$ axis.). Can you see how it works? Look at the following graph for a while:

-
Interesting way to look at it, thank you for taking the time to do the plot. It is slightly going over my head, I'll have to take another look & read when I get home tonight. – ConfusingCalc Sep 26 '13 at 19:16
@ConfusingCalc I will add something to the graph. – Pedro Tamaroff Sep 26 '13 at 19:17