A Discrete Mathematics book from which I'm self-studying ("Discrete Mathematics and Its Applications", by Kenneth Rosen) asks me to do the following:
Given the following recurrence relation:
$C_n = n + 1 + \frac{2}{n}\sum_{k=0}^{n-1}C_k$
The book asks me to show that the sequence $\{C_n\}$, with base case $C_0 = 0$, also satisfies the recurrence relation $nC_n=(n+1)C_{n-1}+2n$ for $n=1,2,\cdots$.
I tried to solve it by induction. For this, I wrote the second recurrence relation for $n+1$:
$(n+1)C_{n+1} = (n+2)C_{n} + 2n + 2$
Then, assuming that the first recurrence relation holds for $n$, I tried to substitute $C_n = n + 1 + \frac{2}{n}\sum\limits_{k=0}^{n-1}C_k$ in the above equation, to see if I obtain $C_{n+1} = n + 2 + \frac{2}{n+1}\sum\limits_{k=0}^{n}C_k$.
$\begin{align*} (n+1)C_{n+1} &= (n+2)C_{n} + 2n + 2\\ (n+1)C_{n+1} &= (n+2)\left( n + 1 + \frac{2}{n}\sum_{k=0}^{n-1}C_k \right ) + 2n + 2\\ (n+1)C_{n+1} &= n(n+2) + n + 2 + \frac{2(n+2)}{n}\sum_{k=0}^{n-1}C_k + 2n + 2\\ (n+1)C_{n+1} &= n^2 + 5n + 4 + \frac{2(n+2)}{n}\sum_{k=0}^{n-1}C_k\\ (n+1)C_{n+1} &= (n+1)(n+4) + \dfrac{2(n+2)}{n}\sum_{k=0}^{n-1}C_k\\ C_{n+1} &= n+4 + \dfrac{2(n+2)}{n(n+1)}\sum_{k=0}^{n-1}C_k \end{align*}$
From this point, I'm not sure how to proceed.