Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Summation algorithms

  1. Feb 27, 2010 #1
    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.

    [tex]\sum^{lgn - 1}_{i = 0}\frac{n}{lgn - i}[/tex] = [tex]n\sum^{lgn}_{i = 1}\frac{n}{i}[/tex]

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

    any clue?

  2. jcsd
  3. Feb 27, 2010 #2


    User Avatar
    Gold Member

    Re: Summation

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

    [tex]\sum_{i=0}^{\lg{(n)} - 1}\frac{n}{\lg{(n)} - i}[/tex]

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

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

    As desired.
  4. Feb 27, 2010 #3
    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!!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook