Why does $\sum_{i=0}^{n-1} \frac{1}{n-i} = \sum_{i=1}^{n }\frac{1}{i}$?

Question

From CLRS Problem 4.3, part 5 . Why does the following holds? $$\sum_{i=0}^{n-1} \frac{1}{n-i} = \sum_{i=1}^{n }\frac{1}{i}. $$

Answer 1

For change of indices, when it seems confusing I find it helpful to write out the first few terms, and if a finite sum, the last term or two, to see the pattern in the numbers as well as the variables.

$$ \sum_{i=0}^{n-1} \frac{1}{n-i} = {1\over n-0} + {1\over n-1} +{1\over n-2} +\cdots +{1\over n-(n-2)} +{1\over n-(n-1)} $$

$$ ={1\over n} + {1\over n-1} +{1\over n-2} +\cdots +{1\over 2} +{1\over 1} $$

$$ ={1\over 1} +{1\over 2} +\cdots + {1\over n-2} + {1\over n-1} +{1\over n} $$

$$ = \sum_{i=1}^{n }\frac{1}{i}.$$

Answer 2

One may perform the change of index $$ k=n-i, \quad \text{new bounds:}\quad k=n-(n-1)=1,\quad k=n-0=n, $$ giving $$ \sum_{i=0}^{n-1} \frac{1}{n-i} =\sum_{k=1}^{n }\frac{1}{k}. $$ The latter sum is known as an harmonic number.