<s>[INST] Recurrence relation $C_n = n + 1 + \dfrac{2}{n}\sum\limits_{k=0}^{n-1}C_k$. 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.
 [/INST] $C_n=n+1+(2/n)\sum^{n-1}$; $nC_n=n^2+n+2\sum^{n-1}$; $$nC_n-(n+1)C_{n-1}=n^2+n-((n-1)C_n-2\sum^{n-2})=n^2+n-((n-1)^2+(n-1))=2n$$
</s>