# Homework Help: Problem with summation, how did he find this result?

1. Oct 22, 2011

### Jncik

1. The problem statement, all variables and given/known data

Hi

I was trying to understand an algorithm analysis problem and I came to this point:

[PLAIN]http://img820.imageshack.us/img820/1834/unledytw.png [Broken]

can someone explain me what he did there? Is there any other step between that should have been written in order for it to be more comprehensible?

Last edited by a moderator: May 5, 2017
2. Oct 22, 2011

### Mr.Miyagi

There may be a relevant identity, but in any case you can write out the first double summation and rearrange the terms in order to get the second equality.

(2/2 + 2/3 + ... 2/n) + (2/2 + 2/3 + ... 2/(n-1)) + ... + (2/2)
= (n-1)*2/2 + (n-2)*2/3 + ... + 1*2/n

All that remains is to convince yourself that this is actually what the second line reads.

3. Oct 22, 2011

### LCKurtz

You are summing over a triangle in the k-i plane:

[URL]http://math.la.asu.edu/~kurtz/pix/doublesum.jpg[/URL]

It is just like reversing the order of integration in a double integral. You can read the limits from the picture.

Last edited by a moderator: May 5, 2017