0
$\begingroup$

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

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

1 Answer 1

1
$\begingroup$

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\;. $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .