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).
Best Answer
$$\sum_{k=1}^n \frac{1}{k+1} = \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n+1}.$$ So if we compare this to $$H_n = \sum_{k=1}^n \frac{1}{k} = 1 + \frac{1}{2} + \cdots + \frac{1}{n},$$ we can see that in the first sum we are missing the first term $1$, and we have an extra last term, $\frac{1}{n+1}$. Therefore, $$\sum_{k=1}^n \frac{1}{k+1} = H_n - 1 + \frac{1}{n+1}.$$ Then $$\begin{align} C_n &= 2(n+1) \sum_{k=1}^n \frac{1}{k+1} \\ &= 2(n+1) \left( H_n - 1 + \frac{1}{n+1} \right) \\ &= 2(n+1)H_n - 2(n+1) + 2 \\ &= 2(n+1)H_n - 2n. \end{align}$$