0
$\begingroup$

I'm having trouble understanding why this identity holds:

$$\sum_{k=0}^{(\log n) - 1} \frac{n}{\log (n - k)} + \theta(1) = \sum_{k=1}^{\log n} \frac{n}{k}+ \theta(1) $$

Any pointers to a proof would be very appreciated.

  • 1
    Are there some floor functions involved?2011-10-24
  • 1
    Are you sure you don't mean $$\sum_{k=0}^{\log(n) - 1} \frac{n}{\log(n) - k} = \sum_{k=1}^{\log(n)} \frac{n}{k}$$ In any case, how are you defining a sum with a non-integer limit?2011-10-24
  • 0
    @the-chaz I think you're right. This is related to proving bounds for functions. I've seen the equation in a couple of different places, but I'm getting the feeling that it's not a strict equality but a short-hand.2011-10-24
  • 0
    @robjohn No this is the form I've seen the equation in. What I left out of the equation is that there is also a constant factor on each side. updating post to reflect that.2011-10-24

2 Answers 2