# Summation algorithms

1. Feb 27, 2010

### 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,

2. Feb 27, 2010

### jgens

Re: Summation

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.

3. Feb 27, 2010

### unknown_2

Re: Summation

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!!