# Concrete Mathematics: Clarifying expressing sum in terms of $H_n$ leading to equation 2.14

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).

• Nope: the $2(n+1)$ also distributes to the $-\frac n{n+1}$ part of the sum. Commented Sep 21, 2020 at 5:47
• Ah ok, so it could be viewed as $2(n+1)(H_n - \frac{n}{n+1})$ Commented Sep 21, 2020 at 5:50

$$\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}
• To close the loop: My confusion was from the fact I did not realise I needed to distribute the $2(n+1)$ to the $-\frac n{n+1}$ part as well. I was just multiplying it with $H_n$ Commented Sep 22, 2020 at 5:13