Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

4 Answers 4

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.

share|improve this answer

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

share|improve this answer

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

share|improve this answer

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.