Generación de series de números catalanes

Question

Los números catalanes pueden definirse como sigue: $C_0=1$ y $$C_{n+1}=\sum_{k=0}^n C_k C_{n-k}\, .$$

Una forma de calcular estos números es introducir la serie generadora $f(x)=\sum_{n\geq 0} C_n x^n$ . Tras algunas manipulaciones formales, se obtiene que $f(x)$ es la misma que la serie de potencias para $\frac{1-\sqrt{1-4x}}{2x}\cdot$ Esto permite calcular $C_n$ explícitamente, a saber $C_n=\frac{(2n)!}{n!(n+1)!}\cdot$ De esta fórmula se deduce fácilmente que el radio de convergencia de la serie $f(x)$ es efectivamente positivo, por lo que todas las manipulaciones formales están justificadas a posteriori . (Por supuesto, no hay necesidad de hacer eso si uno está preparado para usar series formales; pero digamos que uno está tratando de construir un ejercicio para estudiantes de pregrado).

Ahora, esta es la pregunta:

¿Alguien sabe cómo probar directamente que $f(x)$ tiene un radio de convergencia positivo, utilizando únicamente la definición anterior de los números catalanes?

Obsérvese que si se conoce la interpretación combinatoria del $C_n$ como el número de expresiones que contienen $n$ pares de paréntesis que coinciden correctamente, entonces es bastante obvio que $C_n\leq \left(\begin{matrix} 2n\\ n\end{matrix} \right)\leq 4^n$ y todo está bien. Pero me gustaría tener una prueba "puramente analítica".

Answer 1

Aquí hay una posible línea de ataque que dará el resultado deseado si podemos demostrar el siguiente lema (verdadero)

Lema: Para todo $n>1$ $$\sum_{k=1}^{n-1} \frac{1}{k^{3/2}(n-k)^{3/2}} \leq \frac{2}{n^{3/2}}$$

Supongamos que $C_k \leq \frac{4^k}{k^{3/2}}$ para $k=1,2,\ldots, n$ entonces

$$C_{n+1} \leq 4^{n}\left(\frac{2}{n^{3/2}} + \sum_{k=1}^{n-1} \frac{1}{k^{3/2}(n-k)^{3/2}}\right) \leq \frac{4^{n+1}}{(n+1)^{3/2}}$$

por el lema anterior y el límite asumido en $C_k$ se deduce por inducción. Este resultado da

$$\left|\sum_{k=0}^n C_k x^k\right| \leq 1 + \sum_{k=1}^n \frac{(4x)^k}{k^{3/2}}$$

y se deduce que la serie converge para $|x| < \frac{1}{4}$ .

Answer 2

Dejemos que $u_N(z) = \sum_{k=0}^N C_k z^k$ , un polinomio, así que no hay que preocuparse por la convergencia. Utilice la relación de recurrencia para demostrar que $z u_N(z)^2 = u_N(z) -1 + O(|z|^{N+1})$ . Esto motiva a mirar la ecuación $z g(z)^2 = g(z) - 1$ que tiene solución $g(z) = (1 - \sqrt{1-4z})/(2z)$ . Esto (después de eliminar la singularidad removible en $0$ ) es una función analítica en el disco $|z|<1/4$ y su serie de Maclaurin satisface la misma recurrencia y tiene término constante $1$ por lo que los coeficientes son $C_k$ . El radio de convergencia es $1/4$ porque esa es la distancia desde $0$ a la singularidad no removible más cercana.

Answer 3

El paso de inducción de Winther sólo muestra que $C_{n+1}<4^{n+1}/n^{3/2}$ que tiene el denominador equivocado. El lado derecho del lema tiene que ser $\frac{4}{(n+1)^{\frac{3}{2}}}-\frac{2}{n^{\frac{3}{2}}}$ . El problema de la convergencia de la función generadora de números catalanes para ser probado puramente sobre la base de la fórmula de recurrencia fue propuesto por Marshall Hall en su libro Combinatorial Theory, p.20. Lo caracteriza como... "muy difícil", y no ofrece ninguna solución.

Ahora he descubierto que el lema es FALSO. Si n=10 el lado izquierdo es igual a 0,15.... y el lado derecho es igual a 0,063... Por lo tanto, mi supuesta corrección es aún más falsa. Así, el problema sigue sin resolverse...

Answer 4

Perdonad que haya reventado el hilo, pero yo también estaba preocupado por este tema.

Encontré algo interesante en un artículo, remanipulando los argumentos de Winther, para terminar con una prueba válida : https://arxiv.org/pdf/1511.08555.pdf (páginas 4-fin)

El autor consigue demostrar $R\geqslant1/6$ que es suficiente para comparar la función generadora y $\displaystyle\frac{1-\sqrt{1-4x}}{2x}$ en el disco abierto $B(0,1/6)$ para luego obtener la fórmula de $C_n$ y calcular después el radio exat (que no nos importa al establecer la fórmula para $C_n$ ).

Lo dejaré aquí para los próximos que necesiten una solución.

Answer 5

Así es como se encuentra el radio de convergencia. Puedes utilizar la identidad

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

y el prueba de raíz que da

$$ 4 |x| < 1 \implies |x|< \frac{1}{4}. $$

Ver aquí .