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.

  • 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

4

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

  • 0
    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.2011-10-25
0

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.