Harmonic series in the form of $ \sum_{i=0}^{n-1} \frac{1}{n-i} $

Question

I am searching for a solution for a recurrence which ends up in this form: $$\sum_{j=0}^{\log{n}-1}\frac{1}{\log{n}-j} $$ After substituting $m = logn$ the next step I can find is: $$\sum_{j=0}^{m-1}\frac{1}{m-j} = \sum_{j=1}^{m}\frac{1}{j}$$ However I can't seem to find an explanation about how this works. Is this correct and if yes, why?

Answer 1

As $j$ runs from $0$ up to $m-1$ in the first summation, $k=m-j$ runs from $m$ down to $1$, so you’re just calculating

$$\frac1m+\frac1{m-1}+\ldots+\frac12+\frac11\;;$$

this is clearly the same as $\sum_{j=1}^m\frac1j$. In effect you’re doing a substitution $k=m-j$ and noting that the $k$ runs from $m$ to $1$ as $j$ runs from $0$ to $m-1$, so that

$$\sum_{j=0}^{m-1}\frac1{m-j}=\sum_{k=1}^m\frac1k\;,$$

and then renaming the index back to $j$.

Answer 2

Just use the order-reversing property,

$$\sum_{j=1}^m a_j=\sum_{j=1}^m a_{m-j+1}$$ and to better understand it, take $m=4$,

LHS: $$\sum_{j=1}^4 a_j=a_1+a_2+a_3+a_4$$

RHS: $$\sum_{j=1}^4 a_{5-j}=a_4+a_3+a_2+a_1$$

Back to your question,

$$\sum_{j=0}^{m-1}\frac1{m-j}=\sum_{j=1}^{m}\frac1{m-j+1}=\sum_{j=1}^{m}\frac1{m-(m-j+1)+1}=\sum_{j=1}^m\frac1j$$