Identidad binomial que surge de la recurrencia catalana.

Question

La siguiente identidad aparece justo al final de la respuesta a otra pregunta que hice: https://math.stackexchange.com/a/4019598/155881 .

$$F(x) = \frac{1}{\sqrt{1-4x}} \left(\frac{1- \sqrt{1-4x}}{2x}\right)^n = \sum\limits_{k=0}^{\infty}{n+2k \choose k}x^k$$

No se ha podido probar esto. Conocemos las expansiones de ambos términos en el lado izquierdo, haciendo la identidad:

$$\left(\sum\limits_{j=0}^{\infty} \left(\binom{n+2j-1}{j} - \binom{n+2j-1}{j-1}\right)x^j\right) \left(\sum\limits_{l=0}^{\infty}{2l \choose l} x^l\right) = \sum\limits_{k=0}^{\infty}{2n+k \choose k}x^k$$

---

Mi intento: Una cosa obvia es intentar una convolución del lado izquierdo y equiparar los coeficientes de $x^k$ (utilizando también una expresión alternativa para el primer sumatorio en el producto del lado izquierdo):

$$\sum\limits_{l=0}^k {n+2l-1\choose l}\frac{l}{n+l} {2k-2l\choose k-l} = {2n+k\choose k}$$

No estoy seguro de cómo avanzar en esto. Expandir los términos del binomio no lleva a ninguna parte.

Answer 1

Pretendemos demostrar que con

$$Q(z) = \frac{1}{\sqrt{1-4z}} \left(\frac{1-\sqrt{1-4z}}{2z}\right)^n$$

tenemos

$$[z^k] Q(z) = {n+2k\choose k}.$$

Ahora con la rama cortada en $[1/4, \infty)$ para $\sqrt{1-4z}$ tenemos la analiticidad de $Q(z)$ en una vecindad del origen (nótese que el término exponenciado no tiene de hecho un polo en $z=0$ ) y se aplica la fórmula del coeficiente de Cauchy se aplica la fórmula del coeficiente de Cauchy. Obtenemos

$$[z^k] Q(z) = \frac{1}{2\pi i} \int_{|z|=\varepsilon} \frac{1}{z^{k+1}} \frac{1}{\sqrt{1-4z}} \left(\frac{1-\sqrt{1-4z}}{2z}\right)^n \; dz.$$

Ponemos $\sqrt{1-4z} = w$ para que $\frac{1}{\sqrt{1-4z}} \; dz = -\frac{1}{2} \; dw$ y $z=(1-w^2)/4.$ Con $w = 1 - 2z - \cdots$ obtenemos como imagen de $|z|=\varepsilon$ un contorno que serpentea $w=1$ en sentido contrario a las agujas del reloj una vez y se puede deformar a un círculo, por lo que obtenemos

$$[z^k] Q(z) = -\frac{1}{2} \frac{1}{2\pi i} \int_{|w-1|=\gamma} \frac{4^{k+1}}{(1-w^2)^{k+1}} (1-w)^n \frac{1}{2^n} \frac{4^n}{(1-w^2)^n} \; dw \\ = \frac{(-1)^k \times 2^{n+2k+1}}{2\pi i} \int_{|w-1|=\gamma} \frac{(w-1)^n}{(w^2-1)^{n+k+1}} \; dw \\ = \frac{(-1)^k \times 2^{n+2k+1}}{2\pi i} \int_{|w-1|=\gamma} \frac{1}{(w-1)^{k+1}} \frac{1}{(w+1)^{n+k+1}} \; dw \\ = \frac{(-1)^k \times 2^{k}}{2\pi i} \int_{|w-1|=\gamma} \frac{1}{(w-1)^{k+1}} \frac{1}{(1+(w-1)/2)^{n+k+1}} \; dw$$

Aplique el teorema del residuo de Cauchy para obtener

$$(-1)^k \times 2^k \times (-1)^k \frac{1}{2^k} {n+k+k\choose n+k} = \bbox[5px,border:2px solid #00A000]{ {n+2k\choose k}}$$

como se ha reclamado.

Answer 2

Definir $$ F_n(x):=\sum_{k=0}^\infty c_{n,k}x^k \tag{1} $$ donde $$ c_{n,k}:={n+2k \choose k}. \tag{2} $$ Verificar la identidad binomial $$ c_{n+1,k-1}=c_{n,k}-c_{n-1,k}. \tag{3} $$ Definir $$ b:=\frac{1-\sqrt{1-4x}}{2x}, \quad a:=\frac1x-b. \tag{4} $$ Verifique que $$ a+b = a\,b = \frac1x, \quad x\,b^2 = b-1. \tag{5} $$ Tenga en cuenta que $$ a-b = \frac{\sqrt{1-4x}}x. \tag{6} $$ Ecuación $(5)$ implica $$ x\,b^{n+1} = b^n-b^{n-1}. \tag{7} $$ Definir $$ G_n(x) := \frac{b^n}{x(a-b)}. \tag{8} $$ Ecuación $(7)$ implica $$ x\,G_{n+1}(x) = G_n(x)-G_{n-1}(x). \tag{9} $$ Comprueba que los coeficientes de la serie de potencias $\,G_n(x)\,$ satisfacen la misma recurrencia que la ecuación $(3)$ .

Compruebe también que $$ G_{-1}(x) = F_{-1}(x),\quad G_0(x) = F_0(x). \tag{10} $$ Así, $\,F_n(x) = G_n(x)\,$ para todos los enteros $\,n\,$ utilizando la recursividad y hacia atrás.

Answer 3

También se puede demostrar esto mostrando que ambos lados son expresiones diferentes para la función generadora de la misma secuencia.

Fijar un número entero positivo $n$ a partir de ahora. Para un entero no negativo $m$ , dejemos que $Q_m$ es el número de caminos de la red que tocan la diagonal principal (empezando por la esquina inferior izquierda) exactamente $n$ veces antes de que lo supere por primera vez en un $m\times m + 1$ rejilla ( $m$ horizontal, $m+1$ vertical). Llamemos a estas trayectorias caminos admisibles . Todos los caminos considerados aquí sólo pueden ir hacia la derecha o hacia arriba.

Si tal camino admisible existe para algún $m$ entonces $m\ge n$ ya que por cada vez que toques la diagonal, desde la esquina inferior hasta la última vez que tocaste la diagonal pero no subiste (es decir, n veces) necesitas un segmento horizontal que te mantenga por debajo de ella. Por lo tanto, horizontalmente necesitas al menos $n$ segmentos, por lo que $m\ge n$ .

La función generadora tiene entonces este aspecto: $\displaystyle\sum_{m\ge n} Q_mx^m$ .

Definir $k = m - n$ . Tenemos:

Reclamación: Existe una biyección entre las trayectorias admisibles y las trayectorias de un $k\times (n + k)$ rejilla ( $k$ horizontal, $n + k$ segmentos verticales).

Prueba: Dada una trayectoria admisible, eliminamos de ella los siguientes segmentos: el $n$ segmentos horizontales que siguen un punto de fallo y el único segmento vertical que sigue la primera vez que se cruza (es decir, el primer segmento que está por encima de la diagonal). Concatenamos los trozos resultantes pegando sus puntos extremos uno con otro. Obsérvese que el primer segmento que eliminamos siempre es el primer segmento horizontal de la esquina inferior izquierda.El camino que queda tiene $m - n = k$ segmentos horizontales y $m + 1 - 1 = m = n + k$ caminos verticales. Por lo tanto, estas trayectorias sí están en la cuadrícula buscada.

Si tenemos un camino de este tipo $P$ para leer la trayectoria admisible correspondiente empezamos poniendo un segmento horizontal y seguimos $P$ hasta llegar a la diagonal principal, en cuyo punto ponemos otro segmento horizontal, y procedemos a leer $P$ . Ponemos segmentos horizontales hasta tocar la diagonal $n$ veces (sin contar el punto inicial). En ese momento ponemos un segmento vertical, y copiamos lo que queda de $P$ . Invirtiendo los cálculos anteriores vemos que se trata efectivamente de un camino en una red de $m\times m + 1$ .

Obsérvese que como nuestro camino $P$ sube $n + k$ veces debemos ser capaces de empujarla siempre horizontalmente (forzarla a fallar), contando el primer segmento desde la esquina inferior izquierda, n veces ya que, en el peor de los casos (k = 0) después de empujar las n veces conseguimos que se haya movido $n + k$ en ambas direcciones y todavía tenemos el espacio extra para empujar hacia arriba una vez más. Esto demuestra que el camino construido desde $P$ es efectivamente admisible. Esto concluye demostrando que esta correspondencia es en realidad una biyección. $\blacksquare$

Aquí hay un dibujo que muestra esto para $n =2, m = 3, k = 1$ :

[Los bordes amarillos son los que añadimos para asegurarnos de que falla hasta que queramos que tenga éxito]

Hemos demostrado entonces que la función generadora es

$$\begin{equation*} \displaystyle\sum_{m\ge n} Q_mx^m = \displaystyle\sum_{k\ge 0} \binom{n + 2k}{k}x^{n + k}. \end{equation*}$$

Por otro lado, podemos olvidarnos del tamaño de la cuadrícula final (es decir, de $m$ ) y construir lo que sucede a partir de los primeros principios. Hay $n + 1$ sucesos independientes: lo que ocurre antes del primer fallo, entre el primer y el segundo fallo, hasta lo que ocurre entre el $n - 1$ fracaso y el momento del éxito y, a continuación, lo que ocurre después de cruzar la diagonal y pasar por encima por primera vez.

Cada uno de los primeros eventos independientes es algún número catalán $C_{i}$ y contribuye $i + 1$ a las longitudes horizontales y verticales, ya que no debemos cruzar la subdiagonal hasta el momento adecuado. Obsérvese que esto es importante, ya que si sólo consideramos la $i\times i$ En cambio, podríamos tener fallos intermedios entre los puntos finales, ya que se permite que las rutas catalanas toquen la diagonal del cuadrado en el que viven, y no queremos esos fallos adicionales.

Por lo tanto, la función generadora de cada uno de estos eventos es $x\displaystyle\sum_{i = 0}C_ix^i$ (el extra $x$ es el desplazamiento en la contribución a la longitud horizontal). Tenemos $n$ de estos.

Entonces, después de hacer el último cuadrado catalán, tenemos un segmento vertical enfocado y luego lo que queramos siempre que pase en un $j\times j$ cuadrado para algunos $j$ . (Esto se debe a que al final, la cuadrícula final tiene que ser $m\times m + 1$ y la parte catalana ha producido una retícula cuadrada y la franja vertical toma el $+1$ por lo que necesitamos otro cuadrado para que las dimensiones coincidan. La función generadora de este cuadrado es $$\begin{equation*} \displaystyle\sum_{j\ge 0} \binom{2j}{j}x^j \end{equation*}$$ De este modo, hemos demostrado la igualdad $$\begin{equation*} \left(x\displaystyle\sum_{i = 0}C_ix^i\right)^n\displaystyle\sum_{j\ge 0} \binom{2j}{j}x^j = \displaystyle\sum_{k\ge 0} \binom{n + 2k}{k}x^{n + k} \end{equation*}$$ Utilizando lo que sabemos $$\displaystyle\sum_{i = 0}C_ix^i = \dfrac{1 - \sqrt{1 - 4x}}{2x}$$ y, a partir del teorema del Binomio de Newton, que $$ \displaystyle\sum_{j\ge 0} \binom{2j}{j}x^j = \dfrac{1}{\sqrt{1 - 4x}} $$ concluimos $$ \begin{equation*} x^n\left(\dfrac{1 - \sqrt{1 - 4x}}{2x}\right)^n\dfrac{1}{\sqrt{1 - 4x}} = \displaystyle\sum_{k\ge 0} \binom{n + 2k}{k}x^{n + k}, \end{equation*} $$ y anulando el factor $x^n$ en ambos lados obtenemos la igualdad deseada.

Answer 4

Este es un enfoque basado en la _Teorema de inversión de Lagrange . Seguimos el documento Inversión de Lagrange: cuándo y cómo_ por R. Sprugnoli etal.

Consideramos la función generadora \begin {align*} F(x)= \sum_ {k=0}^{ \infty }a_kx^k= \sum_ {k=0}^ \infty\binom {n+2k}{k}x^k \end {align*} y aplicar la fórmula (G6) del documento. La fórmula (G6) dice que si hay funciones $A(u)$ y $\phi(u)$ para que el coeficiente $a_k$ admite una representación \begin {align*} a_k=[u^k]A(u) \phi (u)^k \end {align*} entonces lo siguiente es válido: \begin {align*} F(x)&= \sum_ {k=0}^{ \infty }[u^k]A(u) \phi (u)^kx^k \\ &= \left.\frac {A(u)}{1-x \phi ^{ \prime }(u)} \right |_{u=x \phi (u)} \tag {1} \end {align*}

Obtenemos \begin {align*} \color {azul}{F(x)}& \color {azul}{= \sum_ {k=0}^ \infty\binom {n+2k}{k}x^k} \\ &= \sum_ {k=0}^ \infty [u^k](1+u)^{n+2k}x^k \tag {2} \\ &= \left.\frac {(1+u)^n}{1-x\}, \frac {d}{du}(1+u)^2} \right |_{u=x(1+u)^2} \tag {3} \\ &= \frac {(1+u)^n}{1- \frac {u}{(1+u)^2} \cdot 2(1+u)} \tag {4} \\ &= \frac {(1+u)^{n+1}}{1-u} \tag {5} \\ &= \frac { \left ( \frac {1}{2x} \left (1- \sqrt {1-4x} \right ) \right )^{n+1}}{2- \frac {1}{2x} \left (1- \sqrt {1-4x} \right )} \tag {6} \\ &\,\, \color {azul}{= \frac {1}{ \sqrt {1-4x}} \left ( \frac {1- \sqrt {1-4x}}{2x} \right )^n} \tag {7} \end {align*} y la afirmación es la siguiente.

Comentario:

• En (2) utilizamos el coeficiente de operador $[x^k]$ para denotar el coeficiente de una serie. Observamos que podemos aplicar el teorema de la inversión de Lagrange con $A(u)=(1+u)^n$ y $\phi(u)=(1+u)^2$ .

• En (3) utilizamos la fórmula (1) con $A$ y $\phi$ como se indica en el comentario anterior.

• En (4) sustituimos $x=\frac{u}{1+u}$ y hacer la derivación.

• En (5) simplificamos la expresión.

• En (6) recordamos $u=x(1+u)^2$ que es una ecuación cuadrática en $u=u(x)$ . Calculamos \begin {align*} u(x)&= \frac {1}{2x} \left (1-2x \pm\sqrt {1-4x} \right ) \\ &= \frac {1}{2x} \left (1 \pm\sqrt {1-4x} \right )-1 \end {align*} y tomar la solución con el signo menos, ya que ésta se puede expandir como función generadora.

• En (7) volvemos a hacer algunas simplificaciones para obtener la forma deseada.