Changing indexes of sum with lg

Question

I've seen the following equation (in CLRS Instructor’s Manual, page 4-12):

$$ \sum_{i=0}^{\lg{n}-1}\frac{n}{\lg{n}-i} = n\sum_{i=1}^{\lg{n}}\frac{n}{i}= n\sum_{i=1}^{\lg{n}}\frac{1}{i} $$

I can't seem to understand these transitions. The $n$ was brought out of the sum, thus we can get $$ = n\sum_{i=0}^{\lg{n}-1}\frac{1}{\lg{n}-i}$$

I see the summation index change, but I don't understand how it turns $\lg{n}-i$ to $i$

Furthermore, the last transition seems like a mistake. Shouldn't it be $$ = n^2 \sum_{i=1}^{\lg{n}}\frac{1}{i} $$ ?

If that's mistake, maybe the first one is also a mistake?

Answer 1

Note that $$\sum_{i=0}^{t-1} \frac{n}{t-i} = \frac{n}{t} + \frac{n}{t-1} + \cdots + \frac{n}{1} = \sum_{x=1}^{t} \frac{n}{x} = n \sum_{x=1}^{t} \frac{1}{x}.$$ In your problem, $t = \lg(n)$.

Answer 2

Assuming that $n$ is a power of $2$, $n = 2^m$,

$\begin{array}\\ \sum_{i=0}^{\lg{n}-1}\frac{1}{\lg{n}-i} &=\sum_{i=0}^{m-1}\frac{1}{m-i}\\ &=\sum_{i=1}^{m}\frac{1}{m-(m-i)} \qquad\text{replace } i \text{ by } m-i\\ &=\sum_{i=1}^{m}\frac{1}{i}\\ \end{array} $