Me gustaría probar la siguiente relación recursiva para el catalán números: $$\etiqueta{1} C_0=1,\quad C_n=\sum_{i=0}^{n-1}C_iC_{n-i-1}\text {para }n\ge 1 $$ sin combinatoric argumentos, sólo de manera algebraica; y no de generación de función.
Punto de partida: $$\etiqueta{2} C_n:=\frac{1}{n+1}\binom{2n}{n}. $$ El siguiente recursión puede ser también utilizado (ya probado): $$\etiqueta{3} C_0=1,\quad C_n=\frac{2(2n-1)}{n+1}C_{n-1}\text {para }n\ge 1 $$ Tal vez las identidades de los coeficientes Binomiales (wikipedia) son útiles. En particular, el Chu–Vandermonde de identidad, $$\etiqueta{4} \sum _{j=0}^{k}{\binom {m}{j}}{\binom {n-m}{k-j}}={\binom {n}{k}} $$ o $$\etiqueta{4b} \sum _{m=0}^{n}{\binom {m}{j}}{\binom {n-m}{k-j}}={\binom {n+1}{k+1}} $$ podría ser útil.
Lo he intentado? Traté de sustituir la definición (2) en la r.h.s. de (1) para obtener el l.h.s. de (1). Otro intento fue el de tomar $C_{n-1}$ a partir de (1) (conocido por hipótesis de inducción) y probar con (3) recuperar el $C_n$. En ambos casos, aunque me huele a que cada cosa es más o menos relacionados con el yo no puede encontrar los pasos técnicos para hacer el trabajo.
Un combinatoric prueba con Dyck caminos se pueden encontrar aquí, pero esta no es la forma en que estoy tratando de seguir.
EDITAR La respuesta por "Robert Z" es muy buena y bonita, y voy a aceptarlo; si alguien pudiera encontrar una prueba directa sin generalizada coeficiente binomial, me ramadán'aceptar su respuesta en su lugar.
Respuesta
¿Demasiados anuncios?
Primera prueba.
Tenga en cuenta que para $0\leq i\leq n-1$, $$C_iC_{n-i-1}=a(n,i+1)-a(n,i)$$ donde $$a(n,j):=\frac{(2j-n)}{2n(n+1)}\binom{2j}{j}\binom{2(n-j)}{n-j}.$$ Por lo tanto, para $n\geq 1$, $$\begin{align}\sum_{i=0}^{n-1}C_iC_{n-i-1}&= \sum_{i=0}^{n-1}(a(n,i+1)-a(n,i))\\&=a(n,n)-a(n,0)=C_n. \end{align}$$
Segunda prueba.
Tenemos que $$C_n=\frac{2(2n-1)\cdots (n+1)n}{(n+1)!}=2(-4)^n\binom{1/2}{n+1}$$ cuando utilizamos el concepto de coeficiente binomial generalizado.
Por lo tanto, para $n\geq 1$, $$\begin{align}\sum_{i=0}^{n-1}C_iC_{n-i-1}&=4\sum_{i=0}^{n-1}(-4)^i\binom{1/2}{i+1}(-4)^{n-i-1}\binom{1/2}{n-i}\\ &=-(-4)^n\sum_{j=1}^{n}\binom{1/2}{j}\binom{1/2}{n+1-j}\\ &=-(-4)^n\sum_{j=0}^{n+1}\binom{1/2}{j}\binom{1/2}{n+1-j}+2(-4)^{n}\binom{1/2}{n+1}\\ &=0+C_n=C_n\end{align}$$ donde se aplicó la generalizada Chu–Vandermonde de identidad.
