Relación de recurrencia $C_n = n + 1 + \dfrac{2}{n}\sum\limits_{k=0}^{n-1}C_k$ .

Question

Un libro de Matemáticas Discretas del que me estoy autoestudiando ("Matemáticas Discretas y sus Aplicaciones", de Kenneth Rosen) me pide que haga lo siguiente:

Dada la siguiente relación de recurrencia:

$$C_n = n + 1 + \frac{2}{n}\sum_{k=0}^{n-1}C_k$$

El libro me pide que demuestre que la secuencia $\{C_n\}$ con hipótesis de base $C_0 = 0$ también satisface la relación de recurrencia $nC_n=(n+1)C_{n-1}+2n$ para $n=1,2,\cdots$ .

Intenté resolverlo por inducción. Para ello, escribí la segunda relación de recurrencia para $n+1$ :

$$(n+1)C_{n+1} = (n+2)C_{n} + 2n + 2$$

Entonces, suponiendo que la primera relación de recurrencia se cumple para $n$ Traté de sustituir $C_n = n + 1 + \frac{2}{n}\sum\limits_{k=0}^{n-1}C_k$ en la ecuación anterior, para ver si obtengo $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*}$$

A partir de este punto, no estoy seguro de cómo proceder.

Answer 1

Un método más sencillo : $$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$$ para que la diferencia sea :

$$n C_n-(n-1) C_{n-1} = 2n+ 2C_{n-1}$$ que debería darte la recurrencia modificada.

Answer 2

Puedes eliminar la suma del lado derecho restando:

Para $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*}

Para $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*}

Resta $(2)$ de $(1)$ para conseguirlo:

$$ (n + 1) C_{n+1} - n C_{n} = 2n + 2 + 2 C_{n} $$

Simplifica para obtener la recurrencia que deseas:

$$ (n + 1) C_{n+1} = (n + 2)C_{n} + 2n + 2 $$

Answer 3

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

Answer 4

Como han demostrado otras respuestas, el enfoque que has adoptado no es el más sencillo, pero puede funcionar. Observe en primer lugar que la nueva recurrencia es equivalente (después de dividir por $n$ ) a

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

esto será un poco más fácil de trabajar. Asumiré que $(1)$ como hipótesis de inducción y utilizar la recurrencia original para demostrar el siguiente caso de $(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*}$$

que es lo que queríamos. $(1)$ es la recurrencia original; $(2)$ es un truco estándar para demostrar cosas sobre sumas por inducción; $(3)$ es simplemente multiplicar y ajustar el coeficiente de la suma en una forma que coincida con la recurrencia original; $(4)$ utiliza la recurrencia original; y $(5)$ y $(6)$ son sólo álgebra.