Quiero encontrar el término general de la progresión definida por $x_0=1$, $x_1=2$, y $x_n=\binom{2n}{n}-\sum\limits_{i=0}^{n-2}\left(x_i\binom{2n-2-2i}{n-2-i}\right)$. Ya que yo no sé cómo enfocar este problema he intentado haciendo conjeturas, y es el mejor que pude encontrar es dado por $x_n=\binom{2n}{n}-\frac{2^{n-1}(2^{n-1}-1)}{2}$ que da los mismos resultados exactos para $n=1,2,3,4,5$. Aunque esto parece un resumen de no-sentido, que en realidad proviene de una pregunta concreta sobre los gráficos. Voy a añadir los detalles de este concreto punto de vista tan pronto como tengo algo de tiempo.
Respuestas
¿Demasiados anuncios?
Comenzando con $x_0=1, x_1=2$ y el cálculo de acuerdo a la OPs de la recurrencia de la relación un poco más los términos, \begin{align*} x_2&=\binom{4}{2}-\binom{2}{0}x_0=6-1=5\\ x_3&=\binom{6}{3}-\binom{4}{1}x_0-\binom{2}{0}x_1=20-4-2=14\\ x_4&=\binom{8}{4}-\binom{6}{2}x_0-\binom{4}{1}x_1-\binom{2}{0}x_2=70-15-8-5=42 \end{align*} tomamos nota de la secuencia de $(x_n)_{n\geq 0}=(1,1,2,5,14,42,\ldots)$ comienza con el catalán números de $C_{n+1}$ se define como \begin{align*} C_n=\frac{1}{n+1}\binom{2n}{n}\qquad\qquad n\geq 0 \end{align*}
Nos atenemos a esta suerte puede adivinar y así simplificar considerablemente la relación de recurrencia. Ahora afirman que por $n\geq 2$ hemos \begin{align*} \color{blue}{C_{n+1}=\binom{2n}{n}-\sum_{i=0}^{n-2}\binom{2n-2-2i}{n-2-i}C_{i+1}}\tag{1} \end{align*}
Antes de empezar a probar (1) vamos a hacer algunos más simplificaciones. En primer lugar observamos que la suma puede ser escrito como \begin{align*} \sum_{i=0}^{n-2}\binom{2n-2-2i}{n-2-i}C_{i+1}&=\sum_{i=1}^{n-1}\binom{2n-2i}{n-1-i}C_{i}\\ &=\sum_{i=0}^{n-1}\binom{2n-2i}{n-1-i}C_{i}-\binom{2n}{n-1}\\ \end{align*} Aquí nos movemos en el índice para comenzar con $i=1$ y, a continuación, añadimos el término con $i=0$ y restar como compensación. Poner esto en (1) obtenemos \begin{align*} C_{n+1}&=\binom{2n}{n}-\sum_{i=0}^{n-1}\binom{2n-2i}{n-1-i}C_{i}+\binom{2n}{n-1}\\ &=\binom{2n+1}{n}-\sum_{i=0}^{n-1}\binom{2n-2i}{n-1-i}C_{i}\tag{2} \end{align*} Tomando nota de que $\binom{2n+1}{n}-C_{n+1}=\binom{2n+1}{n}-\frac{1}{n+2}\binom{2n+2}{n+1}=\binom{2n+1}{n-1}$ estamos listos para reformular (2) y reclamar:
El siguiente es válido para $n\geq 1$ \begin{align*} \color{blue}{\sum_{i=0}^{n-1}\binom{2n-2i}{n-1-i}C_{i}=\binom{2n+1}{n-1}}\tag{3} \end{align*}
Nos muestran el binomio identidad (3) con la ayuda de funciones de generación. Es conveniente utilizar el coeficiente de operador $[z^n]$ para denotar el coeficiente de $z^n$ en una serie. De esta manera podemos escribir por ejemplo \begin{align*} [z^k](1+z)^n=\binom{n}{k} \end{align*} También utilizamos la conocida generación de la función de los números de catalán \begin{align*} \sum_{n=0}^\infty C_n z^n&=\frac{1-\sqrt{1-4z}}{2z}\\ &=1+z+2z^2+5z^3+14z^4+42z^5+\cdots \end{align*}
Empezamos con el lado izquierdo de (3) y obtener \begin{align*} \color{blue}{\sum_{i=0}^{n-1}}&\color{blue}{\binom{2n-2i}{n-1-i}C_i}\\ &=\sum_{i=0}^\infty[z^{n-1-i}](1+z)^{2n-2i}[u^i]\frac{1-\sqrt{1-4u}}{2u}\tag{4}\\ &=[z^{n-1}](1+z)^{2n}\sum_{i=0}^\infty\left(\frac{z}{(1+z)^2}\right)^i[u^i]\frac{1-\sqrt{1-4u}}{2u}\tag{5}\\ &=[z^{n-1}](1+z)^{2n}\frac{1-\sqrt{1-\frac{4z}{(1+z)^2}}}{\frac{2z}{(1+z)^2}}\tag{6}\\ &=[z^{n-1}](1+z)^{2n+1}\tag{7}\\ &\color{blue}{=\binom{2n+1}{n-1}} \end{align*} y el reclamo de la siguiente manera.
Comentario:
En (4) se le aplica el coeficiente de operador dos veces. También establece el límite superior de la suma a $\infty$ sin cambiar nada, ya que estamos añadiendo ceros (es decir, $\binom{2n-2i}{n-1-i}=0$ si $i>n-1$).
En (5) utilizamos la linealidad del coeficiente de operador y aplicar la regla de $[z^{p-q}]A(z)=[z^p]z^qA(z)$. Hacemos algunos reordenamientos como preparación para el siguiente paso.
En (6) aplicamos la norma de sustitución del coeficiente de operador con $u=\frac{z}{(1+z)^2}$
\begin{align*} A(z)=\sum_{i=0}^\infty a_i z^i=\sum_{i=0}^\infty z^i [u^i]A(u) \end{align*}En (7) vamos a hacer algunas simplificaciones.
En (8) seleccionamos el coeficiente de $z^{n-1}$.
Marko Riedel
Puntos
19255
A partir de $x_0 = 1$ $x_1 = 2$ y la recurrencia de $n\ge 2$
$$x_n = {2n\choose n} - \sum_{q=0}^{n-2} x_q {2n-2-2q\choose n-2-q}$$
se conjetura que
$$x_n = C_{n+1} = \frac{1}{n+2} {2n+2\choose n+1}.$$
La prueba es por inducción y en el caso base se sostiene por la inspección. Para la inducción de paso podemos obtener a partir de la recurrencia
$$\sum_{q=0}^{n-2} \frac{1}{q+2} {2t+2\elegir q+1} {2n-2-2t\elegir n-2-q}.$$
Con poder formal de la serie que hemos
$$\sum_{q=0}^{n-2} \frac{1}{q+2} {2t+2\elegir q+1} [z^{n-2-q}] (1+z)^{2n-2-2t} \\ = [z^{n-2}] \sum_{q=0}^{n-2} \frac{1}{q+2} {2t+2\elegir q+1} z^q (1+z)^{2n-2-2t}.$$
Ahora podemos extender $q$ más allá de la $n−2$ porque no hay ninguna contribución a partir de la suma en ese caso. Este rendimientos
$$[z^{n-2}] (1+z)^{2n-2} \sum_{q\ge 0} \frac{1}{q+2} {2t+2\elegir q+1} z^q (1+z)^{-2t}.$$
Recordamos que
$$\sum_{q\ge 0} C_q w^q = \frac{1-\sqrt{1-4w}}{2}$$
así que
$$\sum_{q\ge 0} C_{p+1} w^q = \frac{1}{w}\left(-1+\frac{1-\sqrt{1-4w}}{2}\right) = \frac{1-2w-\sqrt{1-4w}}{2a^2}.$$
Este rendimientos para nuestros suma
$$[z^{n-2}] (1+z)^{2n-2} \frac{1-2z/(1+z)^2-\sqrt{1-4z/(1+z)^2}}{2z^2/(1+z)^4} \\ = [z^{n-2}] (1+z)^{2n-2} \frac{1+z^2-(1-z)(1+z)}{2z^2/(1+z)^2} = [z^{n-2}] (1+z)^{2n} = {2n\elegir n-2}.$$
Hemos demostrado que
$$x_n = {2n\choose n} - {2n\choose n+2}.$$
Este es
$$x_n = \left(\frac{(n+1)^2}{(2n+2)(2n+1)} - \frac{(n+1)n(n-1)/(n+2)}{(2n+2)(2n+1)}\right) {2n+2\elegir n+1} \\ = \frac{1}{2} \left(\frac{n+1}{2n+1} - \frac{n(n-1)/(n+2)}{2n+1}\right) {2n+2\elegir n+1} \\ = \frac{1}{2(n+2)} \left(\frac{(n+1)(n+2)}{2n+1} - \frac{n(n-1)}{2n+1}\right) {2n+2\elegir n+1} = \frac{1}{n+2} {2n+2\elegir n+1} $$
como se reivindica.
Adenda. Nosotros, además, buscan mostrar que
$$\sum_{q=0}^{n-2} {n\elegir q+2} {n+1\elegir q+1} {2n\elegir 2t+2}^{-1} = \frac{n(n-1)}{n+2}.$$
El LHS es
$$\frac{n! (n+1)!}{(2n)!} \sum_{q=0}^{n-2} \frac{(2t+2)! (2n-2t-2)!}{(p+2)! (q+1)! (n-2-p)! (n-p)!} \\ = \frac{n! (n+1)!}{(2n)!} \sum_{q=0}^{n-2} \frac{1}{q+2} {2t+2\elegir q+1} {2n-2t-2\elegir n-2-q}.$$
Utilizando el resultado de la primera (inducción de paso) esto se simplifica a
$$\frac{n! (n+1)!}{(2n)!} {2n\elegir n-2} = \frac{n(n-1)}{n+2}$$
de nuevo como se reivindica.
