In Concrete Mathematics (Knuth, Patashnik, and Graham) we have an intermediate solution to the quick-sort recurrence of
$$ C_n = 2(n + 1)\sum^n_{k=1}\frac{1}{k + 1} $$
Given the sum part of that resembles the Harmonic summation of $\sum^n_{k=1}\frac{1}{k}$ we can transform the sum part of the intermediate form above to a Harmonic sum thereby providing a "closed form" solution.
The book does this in the following steps
$$ \begin{align} \sum^n_{k=1}\frac{1}{k + 1} &= \sum_{1 \leq k - 1 \leq n}\frac{1}{k} \\ &= \sum_{2 \leq k \leq n+1}\frac{1}{k} \\ &= \left( \sum_{1\leq k \leq n}\frac{1}{k} \right) - \frac{1}{1} + \frac{1}{n+1} = H_n - \frac{n}{n+1} \end{align} $$
I think the $\frac{1}{1} + \frac{1}{n+1}$ terms are to "trim" the resultant the sum so that we can use $H_n$ in its natural form with clean boundary conditions. So $-\frac{1}{1}$ removes the "start" and $\frac{1}{n+1}$ adds on what the $n+1$ boundary condition would have done. Is this what is happening?
And, if you'll indulge me, add on a follow-up question. The eventual, closed form solution is then presented as follows (2.14 in book)
$$ C_n = 2(n + 1)H_n - 2n $$
Where do they get $2n$ from? I would have thought the eventual closed form would then be $C_n = 2(n+1)H_n - \frac{n}{n+1}$ Obviously 2.14 is correct though; maybe I'm being insufficiently creative in my algebraic manipulations (or need more coffee).
