Sea \(C_n , n\geq0\) la sucesion definida recursivamente como sigue:
\(C_0 = 1\) ,
$$C_n = 1 - \sum_{l=0}^{n-1}C_l \left(\begin{matrix}n+1 \ n-l \end{matrix}\right)$$
probar que \(\forall n \geq 0 , C_n = {(-1)}^{n}\)
Tema
No Resuelto, Induccion
La forma cool (robada por mi a otra persona):
Usar induccion global y comparar con el binomio de newton para \((1-1)^n\)
Firma
Quimey
Quimey escribió:
La forma cool (robada por mi a otra persona):
Usar induccion global y comparar con el binomio de newton para \((1-1)^n\)
no sería (1-2)^n ?
la forma cool no.
y la forma no cool? ahora pienso la forma cool
Supongamos que aparece una persona no cool e intenta realizar el problema, quedaria algo como...
Caso Base: \({C}_{0} = {\left( -1 \left)}^{0} = 1\)
Hipotesis Inductiva:
Sea \({C}_{k}\) verdadero, entonces: \(\forall {n} \geq 0\)
$$1 - \sum_{{l}=0}^{{k}-1} \left( {C}_{l} . \left(\begin{matrix}{k}+1 \\ {k}-{l} \end{matrix}\right) \left) = {\left( -1 \left)}^{k}$$
QPQ \(\forall {n} \geq 0\)
$$1 - \sum_{{l}=0}^{{k+1}-1} \left( {C}_{l} . \left(\begin{matrix}{k}+1+1 \\ {k}+1-{l} \end{matrix}\right) \left) = {\left( -1 \left)}^{{k}+1}$$
Realizo las cuentas y separo el termino de la izquierda en \({\left( -1 \left)}^{k} + (-1)\), para aplicar H.I. en el \({\left( -1 \left)}^{k}\).
En la sumatoria del lado derecho, como va desde 0 hasta k, separo el ultimo termino de la sumatoria para dejarla desde 0 hasta (k-1), sumando al final de la misma el termino $${C}_{k} . \left(\begin{matrix}{k}+2 \\ {k}+1-{kl} \end{matrix}\right) \left)$$
, que es igual a \({C}_{k} . \left( {k} + 1 \left)\).
Paso todo para el lodo izquierdo, para igualarlo a 0, junto las dos sumatorias (notemos que por la modificacion, ambas van de 0 hasta (k-1) y me queda...
$$2 - \sum_{{l}=0}^{{k-1}} \left( {C}_{l} . \left( \left( \begin{matrix}{k}+2 \\ {k}+1-{l} \end{matrix} \right) + \left( \begin{matrix}{k}+1 \\ {k}-{l} \end{matrix} \right) \right) - {C}_{k} . \left( {k}+1 \right) = 0$$
Pense en aplicar H.I. sobre el \({C}_{k}\) que me queda, reemplazandolo por el (1-Sumatoria...) o el (-1)^(k+1) pero aun asi, me queda algo mas feo y que noe me esta llevando a nada...
¿Es correcto el camino que esta persona no cool esta siguiendo o deberia encararlo de otro modo? Digo, para comentarle y que se avive (no vayan a pensar que soy yo).
Saludos!
Aca va una forma no cool (medio choclosa)
(uso \(i = l\))
$$C_0 = 1 \quad C_n = 1-\sum_{i=0}^{n-1} C_i {n+1 \choose n-i}$$
Caso base: (\(n=0\)): \(C_0 = 1 = (-1)^0 = 1\).
Paso inductivo:
$$C_{n+1} = 1-\sum_{i=0}^{n} C_i {n+2 \choose n+1-i} = 1-\sum_{i=0}^{n} C_i \left[{n+1 \choose n+1-i} + {n+1 \choose n-i} \right] =$$
$$= 1-\sum_{i=0}^{n} C_i {n+1 \choose n+1-i} - \sum^n_{i=0} C_i {n+1 \choose n-i} =$$
$$= 1-\sum_{i=0}^{n} C_i {n+1 \choose n+1-i} - \sum^{n-1}_{i=0} C_i {n+1 \choose n-i} - C_n {2n \choose 0} =$$
Donde los \(C_n\) se cancelan, quedando:
$$= -\sum^n_{i=0} {n+1 \choose n+1-i}$$
Desarrollando un poco las sumas se puede ver que
$$= -\sum^n_{i=0} {n+1 \choose n+1-i} = -\left[ C_0 {n+1 \choose n+1} + \sum^{n-1}_{i=0} C_{i+1} {n+1 \choose n-i} \right]=$$
Usando ppio de inducción global, ya que \(i+1 \leq n\), y la hipótesis inductiva \(C_i = (-1)^i \qquad \forall i \leq n\)
se tiene que:
$$= -1-\sum^{n-1}_{i=0} (-1)^{i+1}\,{n+1 \choose n-i} = -1-\sum^{n-1}_{i=0}(-C_i) {n+1 \choose n-i}$$
\(-1 + \sum^{n-1}_{i=0} C_i {n+1 \choose n-i} = -C_n = -1 * (-1)^n = (-1)^{n+1} = C_{n+1}\)
Firma
atte. Vassiliev Saveli
Hola, perdón que resucite un topic viejo, pero este ya es el segundo topic que leo sobre este problema y no termino de entenderlo 😕
De lo que escribió Saveli entiendo hasta acá:
saveli escribió:
Donde los \(C_n\) se cancelan, quedando:
\(= -\sum^n_{i=0} {n+1 \choose n+1-i}\)
¿Dónde se fue el \({c}_{i}\) que estaba multiplicando al número combinatorio?
y después en el paso siguiente, ¿por qué la sumatoria va de 0 a n-1? ¿El qué está separado no es el término con i=0?
Gracias