Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

6 Answers 6

up vote 1 down vote accepted

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

share|improve this answer
    
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)$.

share|improve this answer
    
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) $$

share|improve this answer
1  
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

share|improve this answer
    
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)$$

share|improve this answer
    
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:

enter image description here

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.