Concrete Mathematics: Simplification of quick sort recurrence in preparation of finding summation factor

Question

In the analysis of the quicksort algorithm a recurrence is presented in 2.12. I feel I understand the simplification steps down to the point where we have

$$ nC_n - (n - 1)C_{n-1} = 2n + 2C_{n-1},\ \ \ \ \ \text{for}\ n > 2. $$

Then the book says

It turns out that this relation also holds when $n = 1$, because $C_1 = 2$. Therefore the original recurrence for $C_n$ reduces to a much simpler one: $$ \begin{align} C_0 &= 0 \\ nC_n &= (n + 1)C_{n-1} + 2n,\ \ \ \ \ \ \text{for}\ n > 0 \end{align} $$

I don't understand how the fact that the relation holding for $n = 1$ allows for simplification from the first equation (in this question, not the book section) to the second simpler one. How is this transformation done?

Answer 1

By transposing $(n-1)C_{n-1}$ to the righthand side of the first displayed recurrence you already have

$$nC_n=(n+1)C_{n-1}+2n\tag{1}$$

for $n>1$. At $n=1$ this becomes

$$C_1=2C_0+2\,,$$

and since $C_1=2$, setting $C_0=0$ makes $(1)$ true for $n\ge 1$, i.e., for $n>0$.

Answer 2

$$t_n=nC_n-(n+1)C_n=2n \implies \frac{C_n}{n+1}-\frac{C_{n-1}}{n}=\frac{2}{n+1}$$ $$\implies t_n=f_{n}-f_{n-1}=\frac{2}{n+1}$$ By telescopic summation we have $$f_N-f_0=\sum_{n=1}^{N}\frac{2}{n+1} \implies \frac{C_N}{N+1}=2\left(H_N-1+\frac{1}{(N+1)}\right)$$ $$\implies C_N=2(N+1)(H_N-1)+2, N >0$$ Here, $H_N=1+1/2+1/3+1/4+...+1/N$ are harmonic numbers.