Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
Are there some floor functions involved? –  The Chaz 2.0 Oct 24 '11 at 17:47
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? –  robjohn Oct 24 '11 at 17:57
    
@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. –  Zubin Oct 24 '11 at 18:16
    
@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. –  Zubin Oct 24 '11 at 18:17
add comment

2 Answers

The equation is not true in the form given. $$ \begin{align} 1 &=\frac{1}{n}\sum_{k=0}^{\log(n) - 1} \frac{n}{\log(n)}\\ &\le\frac{1}{n}\sum_{k=0}^{\log(n) - 1} \frac{n}{\log(n - k)}\\ &\le\frac{1}{n}\sum_{k=0}^{\log(n) - 1} \frac{n}{\log(n-\log(n))}\\ &=\frac{\log(n)}{\log(n-\log(n))}\\ &\to1 \end{align} $$ However, $$ \begin{align} \frac{1}{n}\sum_{k=1}^{\log(n)} \frac{n}{k} &=\log(\log(n))+\gamma+O\left(\frac{1}{\log(n)}\right)\\ &\to\infty \end{align} $$ On the other hand:

If the equation was as I suggested in my comment above: $$ \sum_{k=0}^{\log(n) - 1} \frac{n}{\log(n) - k} = \sum_{k=1}^{\log(n)} \frac{n}{k} $$ and the upper limits should be treated as a bound for the sum in $k$, not as an actual value to be used, essentially applying $\operatorname{floor}$ to the upper limits, as The Chaz suggested, then $$ \begin{align} \sum_{k=1}^{\lfloor\log(n)\rfloor} \frac{n}{k}-\sum_{k=0}^{\lfloor\log(n)\rfloor - 1} \frac{n}{\log(n) - k} &=\sum_{k=1}^{\lfloor\log(n)\rfloor} \frac{n}{k}-\sum_{k=1}^{\lfloor\log(n)\rfloor} \frac{n}{\log(n) - \lfloor\log(n)\rfloor + k}\\ &=\sum_{k=1}^{\lfloor\log(n)\rfloor}\frac{n(\log(n) - \lfloor\log(n)\rfloor)}{k(\log(n) - \lfloor\log(n)\rfloor + k)}\tag{1} \end{align} $$ Since $0\le\log(n) - \lfloor\log(n)\rfloor<1$ $$ \begin{array}{} \sum_{k=1}^{\lfloor\log(n)\rfloor}\frac{1}{k(k+1)}\le\sum_{k=1}^{\lfloor\log(n)\rfloor}\frac{1}{k(\log(n) - \lfloor\log(n)\rfloor + k)}\le\sum_{k=1}^{\lfloor\log(n)\rfloor}\frac{1}{k^2}\tag{2} \end{array} $$ Thus, $(1)$ is between $$ n(\log(n) - \lfloor\log(n)\rfloor)\left(1-\frac{1}{\lfloor\log(n)\rfloor+1}\right) $$ and $$ n(\log(n) - \lfloor\log(n)\rfloor)\left(\frac{\pi^2}{6}-\frac{1}{\lfloor\log(n)\rfloor+1}\right) $$ So this doesn't match your statement, either, since the difference is $O(n)$.

share|improve this answer
    
Of course, treating the given upper limits "... as a bound for the sum in $k$, not as an actual value to be used" is a perfectly reasonable interpretation/assumption, but it definitely should have been stated in the OP! (+1) for a thorough clearing-up of the confusion. –  The Chaz 2.0 Oct 25 '11 at 2:21
add comment

EDIT: It would also be a good idea to address the questions brought up in comments so far, proper inclusion of floors and parentheses would be very important to this problem and its solution.

I believe that the best way to approach a proof of this equality would be to examine the forms of each element in the sum individually. Looking at what you have posted, I can see that the first and last elements of each sum are equivalent: $$ (k = 0) n/log(n-0) = n/log(n) $$ $$ (k = log(n)) n/k = n/log(n) $$ It seems to me that the same is true for the last & first elements as well. Perhaps this can be proved by showing that these sums are equivalent in general, though in reverse order as given. If that doesn't work, I would try a proof by induction.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.