<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] You can get rid of the sum on the RHS by subtracting:
For $C_{n+1}$:
\begin{align*}
C_{n+1} &= n + 2 + \dfrac{2}{n+1}\sum_{k=0}^{n}C_k \\
(n + 1) C_{n+1} &= (n + 1)(n + 2) + 2 \sum_{k=0}^{n}C_k \tag{1}
\end{align*}
For $C_n$:
\begin{align*}
C_n &= n + 1 + \dfrac{2}{n}\sum_{k=0}^{n-1}C_k \\
n C_n &= n(n + 1) + 2 \sum_{k=0}^{n-1}C_k \tag{2}
\end{align*}
Subtract $(2)$ from $(1)$ to get:
$$
(n + 1) C_{n+1} - n C_{n} = 2n + 2 + 2 C_{n}
$$
Simplify to get the recurrence you want:
$$
(n + 1) C_{n+1} = (n + 2)C_{n} + 2n + 2
$$
</s>