# summation of random variable into harmonic number

In our textbook "Algorithm Design" we are given an example of a deck of $$n$$ cards and we have to guess the correct card, and every time a card is drawn, we remember that cards so we are uniformally guessing only among the cards not yet seen. I don't understand the final part of the following summation, where the authors reduce the summation to a harmonic number... note: the random variable $$X_i$$ takes on 1 if the ith value is correct or 0 otherwise: $$\Pr[X] = \sum\limits_{i=1}^n E[X_i] = \sum\limits_{i=1} ^n \frac {1}{n-i+1} = \sum\limits_{i =1}^n \frac {1}{i}$$ I don't see how they derived $$\sum\limits_{i =1}^n \frac {1}{i}$$, which I know becomes a harmonic number [Ideally someone might show this without calculus]... Thanks

• I think what you have written is incorrect... It should be $\sum_{i=1}^{n-2}i$, no? – K.defaoite May 31 '20 at 13:58

They reindexed the sum. As $$i$$ runs from $$1$$ to $$n$$, $$j=n-i+1$$ runs from $$n$$ to $$1$$, so
$$\sum_{i=1}^n\frac1{n-i+1}=\sum_{j=1}^n\frac1j=\sum_{i=1}^n\frac1i\;.$$