# 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.

-

A simpler method : $$n C_n = n(n + 1) + 2\sum_{k=0}^{n-1}C_k$$ $$(n-1) C_{n-1} = (n-1)n + 2\sum_{k=0}^{n-2}C_k$$ so that the difference is :

$$n C_n-(n-1) C_{n-1} = 2n+ 2C_{n-1}$$ that should give you the modified recurrence.

-

$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$$

-

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$$

-

As other answers have shown, the approach that you took is not the easiest one, but it can be made to work. Note first that the new recurrence is equivalent (after division by $n$) to

$$C_n=\left(1+\frac1n\right)C_{n-1}+2\;;\tag{1}$$

this will be a little easier to work with. I’ll assume $(1)$ as an induction hypothesis and use the original recurrence to prove the next case of $(1)$:

\begin{align*} C_{n+1}&\overset{(1)}=n+2+\frac2{n+1}\sum_{k=0}^nC_k\\ &\overset{(2)}=n+2+\frac2{n+1}\left(C_n+\sum_{k=0}^{n-1}C_k\right)\\ &\overset{(3)}=n+2+\frac2{n+1}C_n+\frac{n}{n+1}\cdot\frac2n\sum_{k=0}^{n-1}C_k\\ &\overset{(4)}=n+2+\frac2{n+1}C_n+\frac{n}{n+1}(C_n-n-1)\\ &\overset{(5)}=n+2+\frac{n+2}{n+1}C_n-n\\ &\overset{(6)}=\left(1+\frac1{n+1}\right)C_n+2\;, \end{align*}

which is what we wanted. $(1)$ is the original recurrence; $(2)$ is a standard trick when proving things about sums by induction; $(3)$ is just multiplying out and adjusting the coefficient of the summation into a form that matches the original recurrence; $(4)$ uses the original recurrence; and $(5)$ and $(6)$ are just algebra.

-
Thank you for the response. There seems to be a typo in the first equation, because it's not being displayed; only an error message "Math Processing Error" appears. Do you mean: $C_n=\left(1+\frac1n\right)C_{n-1}+2$?. –  anonymous Jul 9 '12 at 18:04
@anonymous: Yes. (Sorry about that: it displayed fine in the preview.) –  Brian M. Scott Jul 9 '12 at 18:13