Combinatoria - Números catalanes función recursiva prueba por inducción ayuda

Question

Estoy tratando de demostrar que $$C_n = \sum_{i=0}^{n-1} C_iC_{n-i-1}$$ cuando $1\leq n$ y $C_0 = 1$ por inducción. ( $C_n$ es el $n$ número de catalán).

Para $n=1$ esto es cierto.

Supongamos que es cierto para $n=k$ :

$$C_k = \sum_{i=0}^{k-1} C_iC_{k-i-1}$$

Ahora sólo tenemos que demostrar que $$C_{k+1} = \sum_{i=0}^{k} C_iC_{k-i}$$

Y aquí estoy atascado. No puedo entender cómo usar nuestra suposición.

Un recordatorio amistoso: $C_r = \frac{1}{r+1} {2r \choose r}$ para todos $ 0\leq r$

Answer 1

Hay muchas definiciones diferentes de los números catalanes que aclaran diferentes propiedades. Una de ellas es como el número de formas de poner entre paréntesis el producto $x_1 x_2 \dots x_{n+1}$ , lo que hace que la relación que se quiere demostrar sea obvia. A partir de ahí puedes demostrar que la función generadora $\sum C_n x^n$ es la solución de una ecuación cuadrática en $x$ y tiene una fórmula que implica la raíz cuadrada de alguna función como $\frac{1}{1-x}$ (probablemente no sea exactamente eso, pero sí parecido). Entonces el teorema del binomio para el exponente $1/2$ le indica una fórmula para los coeficientes de la función generadora y muestra que esta definición es equivalente a la numérica.

A iniciar a partir de la definición al final de la pregunta, la fórmula para los números, y probar la recursión parece un problema combinatorio potencialmente complicado. No creo que esta sea la forma en que normalmente se hace, excepto por el bien del deporte o su gemelo malvado, los ejercicios de los estudiantes.