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!