# Summation identity involving logarithm

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.

-
Are there some floor functions involved? –  The Chaz 2.0 Oct 24 '11 at 17:47
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

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)$.

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