La simplificación de catalán número de la recurrencia de la relación

Question

Mientras que la solución de un problema, he reducido en el formulario de la siguiente relación de recurrencia.

$ C_{0} = 1, C_{n} = \displaystyle\sum_{i=0}^{n - 1} C_{i}C_{n - i - 1} $

Sin embargo https://en.wikipedia.org/wiki/Catalan_number me dice, esta es la recurrencia relación a la catalana, números y puede ser más simplificado,

$ C_{0} = 1, C_{n} = \displaystyle\frac {2(2n - 1)}{n + 1} C_{n - 1}$

¿Cómo puedo derivar la segunda relación de la primera ? Es una manera de demostrarlo es a través de la inducción, pero no sabemos la versión simplificada de la recidiva hasta el momento.

Answer 1

Usted probablemente puede encontrar en algún lugar en línea, pero para completar una derivación de la familiar forma cerrada para $C_n$ a partir de la recurrencia $$C_n=\sum_{k=0}^{n-1}C_kC_{n-1-k}\tag{0}$$ and the initial value $C_0$, via the ordinary generating function. Then, as in Mhenni Benghorbal's answer, you can easily (discover and) verify the first-order recurrence. I don't see any nice way to get it directly from $(0)$.

Deje que el ordinario de generación de función para el catalán números

$$c(x)=\sum_{n\ge 0}C_nx^n=\sum_{n\ge 0}\sum_{k=0}^{n-1}C_kC_{n-1-k}x^n\;.$$

Entonces a partir de la $C_0=1$, tenemos

$$\begin{align*} c(x)&=\sum_{n\ge 0}\sum_{k=0}^{n-1}C_kC_{n-1-k}x^n\\ &=1+\sum_{n\ge 1}\sum_{k=0}^{n-1}C_kC_{n-1-k}x^n\\ &=1+x\sum_{n\ge 0}\sum_{k=0}^nC_kC_{n-k}x^n\\ &=1+x\left(\sum_{n\ge 0}C_nx^n\right)^2\\ &=1+xc(x)^2\;, \end{align*}$$

o $xc(x)^2-c(x)+1=0$. La fórmula cuadrática, a continuación, los rendimientos

$$c(x)=\frac{1\pm\sqrt{1-4x}}{2x}\;,\tag{1}$$

y ya

$$\lim_{x\to 0}c(x)=\lim_{x\to 0}\sum_{n\ge 0}C_nx^n=C_0=1\;,$$

es claro que debemos elegir la raíz cuadrada negativa en $(1)$, por lo que

$$c(x)=\frac{1-\sqrt{1-4x}}{2x}\;.$$

Ahora aplique el teorema del binomio para $\sqrt{1-4x}$:

$$\begin{align*} \left(1-4x\right)^{1/2}&=\sum_{n\ge 0}\binom{1/2}n(-4x)^n\\ &=\sum_{n\ge 0}\frac{\left(\frac12\right)\left(-\frac12\right)\left(-\frac32\right)\dots\left(-\frac{2n-3}2\right)}{n!}(-4x)^n\\ &=\sum_{n\ge 0}(-1)^{n-1}\frac{(2n-3)!!}{2^nn!}(-4x)^n\\ &=-\sum_{n\ge 0}\frac{2^n(2n-3)!!}{n!}x^n\\ &=-2\sum_{n\ge 0}\frac{2^{n-1}\prod_{k=1}^{n-1}(2k-1)}{n(n-1)!}x^n\\ &=-2\sum_{n\ge 0}\frac{2^{n-1}(n-1)!\prod_{k=1}^{n-1}(2k-1)}{n(n-1)!^2}x^n\\ &=-2\sum_{n\ge 0}\frac{\left(\prod_{k=1}^{n-1}(2k)\right)\left(\prod_{k=1}^{n-1}(2k-1)\right)}{n(n-1)!^2}x^n\\ &=-2\sum_{n\ge 0}\frac{(2n-2)!}{n(n-1)!^2}x^n\\ &=-2\sum_{n\ge 0}\frac1n\binom{2(n-1)}{n-1}x^n\;, \end{align*}$$

donde el término constante es $1$ y por lo tanto el término constante en la suma que en realidad es $-\frac12$. Por lo tanto,

$$\begin{align*} c(x)&=\frac1{2x}\left(1+2\left(-\frac12+\sum_{n\ge 1}\frac1{n}\binom{2(n-1)}{n-1}x^n\right)\right)\\ &=\sum_{n\ge 1}\frac1n\binom{2(n-1)}{n-1}x^{n-1}\\ &=\sum_{n\ge 0}\frac1{n+1}\binom{2n}nx^n\;, \end{align*}$$

y tenemos la familiar forma cerrada $C_n=\dfrac1{n+1}\dbinom{2n}n$.

Answer 2

Un problema relacionado. Es más fácil probar que el uso de la identidad

$$ C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!} \implies C_{n-1}=\frac{(2(n-1))!}{(n)!\,(n-1)!} $$

$$ \frac{C_n}{C_{n-1}}= \frac{ (2n)(2n-1)(2n-2)!(n-1)! }{(n+1)n(n-1)!(2n-2)!}=\frac{2(2n-1)}{n+1} $$

$$ \implies C_n = \frac{2(2n-1)}{n+1} C_{n-1}. $$

Añadido: vamos a encontrar la ordinaria de generación de función. Deje $g(x)=\sum_{n=0}^{\infty}C_{n}x^{n} $

$$ C_{n+1} = \displaystyle\sum_{i=0}^{n } C_{i}C_{n - i } \implies \sum_{n=0}^{\infty}C_{n+1}x^n = \sum_{n=0}^{\infty} \sum_{i=0}^{n } C_{i}C_{n - i } x^n $$

$$ \implies \sum_{n=1}^{\infty}C_{n}x^{n-1} = \sum_{i=0}^{\infty}C_i\sum_{n=i}^{\infty}C_{n-i}x^n= \sum_{i=0}^{\infty}C_i\sum_{n=0}^{\infty}C_{n}x^{n+i}$$

$$\implies \frac{1}{x}\sum_{n=0}^{\infty}C_{n}x^{n}-\frac{C_0}{x}= \sum_{i=0}^{\infty}C_ix^i\sum_{n=0}^{\infty}C_{n}x^{n} $$

$$ \implies \frac{g(x)}{x}-\frac{1}{x} = g(x)g(x) = g(x)^2 $$

$$ \implies g(x)^2-\frac{g(x)}{x}+\frac{1}{x} = 0. $$

Answer 3

Nota: Esta respuesta es simplemente una ligera variación de las respuestas ya dadas. La derivación de la generación de la función de la agencia catalana de los Números es algo diferente que puede ser conveniente para el lector.

El siguiente es válido: La relación de recurrencia \begin{align*} C_{0} = 1, C_{n} = \displaystyle\sum_{i=0}^{n - 1} C_{i}C_{n - i - 1}\qquad(n\geq 1)\tag{1} \end{align*} especifica los Números de catalán \begin{align*} \qquad\qquad\frac{1}{n+1}\binom{2n}{n}\qquad\qquad(n\geq 0)\tag{2} \end{align*}

Nota: La conexión entre el cerrado de la fórmula (2) y la fórmula indicada en la pregunta se da en el comienzo de la respuesta de @MhenniBenghorbal.

La generación de la función de $C_n$:

Cuando se mira la relación de recurrencia vemos que $\sum_{i=0}^{n - 1} C_{i}C_{n - i - 1}$ es de Cauchy-Producto. Desde Cauchy productos se producen cuando se multiplica la serie parece natural para trabajar con las siguientes funciones de generación:

\begin{align*} C(z) = \sum_{n\geq 0}C_nz^n\qquad\text{and}\qquad C^2(z)=\sum_{n\geq 0}\left(\sum_{i=0}^{n}C_iC_{n-i}\right)z^n\tag{3} \end{align*}

Deje $[z^n]$ el valor del coeficiente de operador. Podemos observar con la ayuda de (1) y (3):

\begin{align*} [z^n]C(z)&=C_n\\ &=\sum_{i=0}^{n-1}C_iC_{(n-1)-i}\\ &=[z^{n-1}]C^2(z)\\ &=[z^n]zC^2(z)\qquad\qquad\qquad(n\geq 1)\\ \\ [z^0]C(z)&=C_0=1\\ \end{align*}

Por lo tanto, tenemos

\begin{align*} C(z)=zC^2(z)+C_0=zC^2(z)+1 \end{align*}

y la solución de la ecuación cuadrática da

\begin{align*} C_{1,2}(z)=\frac{1}{2z}\left(1\pm\sqrt{1-4z}\right) \end{align*} Desde la expansión de $\sqrt{1-4z}=1-2z-\ldots$ $C(z)= \sum_{n\geq 0}C_nz^n$ es una potencia de la serie en $z$ llegamos a la conclusión de que la solución siguiente es válido:

\begin{align*} C(z)=\frac{1}{2z}\left(1-\sqrt{1-4z}\right) \end{align*}

Ahora:

Cálculo de $C_n$:

Con la ayuda de el conocido binomio identidad $$\binom{\frac{1}{2}}{n}=\frac{(-1)^{n+1}}{4^n(2n-1)}\binom{2n}{n}$$ tenemos \begin{align*} C_n&=[z^n]\frac{1}{2z}\left(1-\sqrt{1-4z}\right)\\ &=-\frac{1}{2}[z^{n+1}]\sqrt{1-4z}\\ &=-\frac{1}{2}[z^{n+1}]\sum_{n\geq 0}\binom{\frac{1}{2}}{n}\left(-4z\right)^n\\ &=-\frac{1}{2}\binom{\frac{1}{2}}{n+1}\left(-4\right)^{n+1}\\ &=\frac{1}{2}\frac{1}{2n+1}\binom{2n+2}{n+1}\\ &=\frac{1}{2}\frac{1}{2n+1}\frac{(2n+2)(2n+1)}{(n+1)^2}\binom{2n}{n}\\ &=\frac{1}{n+1}\binom{2n}{n} \end{align*}