Problem with summations for sorting algorithm?

According to this lecture http://web.stanford.edu/class/archive/cs/cs161/cs161.1138/lectures/10/Small10.pdf, slide 26, the expected number of comparisons done by quicksort is smaller or equal to $$2n\sum_{k=1}^{n} \frac{1}{k}$$ but I have been taught in class that the expected number of comparisons is equal to $$2\sum_{k=1}^{n-1} \frac{n-k}{k}$$ Could someone tell me where this is derived from? I know that each comparison has probability $\frac{2}{j-i+1}$, for some two numbers $i$ and $j$, as stated in the slides.

$$\sum_{i=1}^n\sum_{j=i+1}^n\frac1{j-i+1}=\sum_{i=1}^n\sum_{k=1}^{n-i}\frac1{k+1}=\sum_{k=1}^{n-1}\sum_{i=1}^{n-k}\frac1{k+1}=\sum_{k=1}^{n-1}\frac{n-k}{k+1}\;.$$
This gives the right result for $n=2$, so it seems that the denominator of the expression you were given in class is off by $1$.
• sorry, but what happened to the factor of $2$ in the front? – gametheorybeginner Mar 21 '16 at 7:57