It can be shown that Cn, the average number of comparisons made by the quick sort algorithm (described in preamble to question $50$ in exercise $5.4),$ when sorting $n$ elements in random order, satisfies the recurrence relation
$$C_{n} = 1 + n + \dfrac{2}{n}\sum_{k=0}^{n-1}C_{k}$$
for $n = 1, 2, \dots,$ with initial condition $C_{0} = 0.$
- Show that $\{C_{n}\}$ also satisfies the recurrence relation $nC_{n} = (n + 1)C_{n-1} + 2n \:\text{for}\: n = 1, 2, \dots$
- Use question $48$ to solve the recurrence relation in part $(A)$ to find an explicit formula for $C_{n}.$
