Summation Algorithm: Understanding n/lgn-i = n/i

[unknown_2]

Hi, I've been looking through my algorithms book/notes and I've come across this summation I'm not quite sure how they got to.

\sum^{lgn - 1}_{i = 0}\frac{n}{lgn - i} = n\sum^{lgn}_{i = 1}\frac{n}{i}

where lgn = log_{2}n, it's just to make it simpler


any clue?

cheers,

 

[jgens]

It looks like you might have an extra factor of n is the second summation. However, consider the sum

\sum_{i=0}^{\lg{(n)} - 1}\frac{n}{\lg{(n)} - i}

Let u = \lg{(n)} - i, then u attains values between 1 and \lg{(n)}. Therefore, summing over this index we find that . . .

\sum_{i=0}^{\lg{(n)} - 1}\frac{n}{\lg{(n)} - i} = \sum_{u=1}^{\lg{(n)}}\frac{n}{u}

As desired.

 

[unknown_2]

yeah I kinda knew the n wasn't supposed to be there, but i put it in just in case i was wrong. your solution makes total sense, thank you very much!