Identidad binomial surgida de la recurrencia catalana.

Buscamos 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$[1/4, \infty)$por$\sqrt{1-4z}$tenemos analitica de$Q(z)$en una vecindad del origen (nótese que el término exponenciado de hecho no tiene un polo en$z=0$) y 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.$$

Nosotros ponemos$\sqrt{1-4z} = w$así que eso$\frac{1}{\sqrt{1-4z}} \; dz = -\frac{1}{2} \; dw$y$z=(1-w^2)/4.$Con$w = 1 - 2z - \cdots$obtenemos como la imagen de$|z|=\varepsilon$un contorno que serpentea alrededor$w=1$en sentido contrario a las manecillas del reloj una vez y puede ser deformado 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 afirma.

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}$$ Verificalo $$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}$$ Verifique que los coeficientes de la serie de potencias $\,G_n(x)\,$satisfacer la misma recurrencia que la ecuación $(3)$.

También verifique que

$$G_{-1}(x) = F_{-1}(x),\quad G_0(x) = F_0(x). \tag{10}$$ Por lo tanto, $\,F_n(x) = G_n(x)\,$para todo entero $\,n\,$utilizando la recursividad hacia adelante y hacia atrás.

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

Fijar un entero positivo$n$de ahora en adelante. Para un entero no negativo$m$, dejar$Q_m$sea ​​el número de caminos de celosía, que tocan la diagonal principal (comenzando desde la esquina inferior izquierda) exactamente$n$veces antes de pasar por encima de él por primera vez en un$m\times m + 1$cuadrícula ($m$horizontal,$m+1$vertical). Llamemos a estos caminos caminos admisibles . Todos los caminos considerados aquí solo pueden ir hacia la derecha o hacia arriba.

Si tal camino admisible existe para algunos$m$luego$m\ge n$ya que cada vez que toca la diagonal, desde la esquina inferior hasta la última vez que toca la diagonal pero no pudo subir (es decir, n veces), necesita un segmento horizontal que lo mantenga debajo de ella. Entonces, horizontalmente necesitas al menos$n$segmentos, por lo tanto$m\ge n$.

La función generadora se ve así:$\displaystyle\sum_{m\ge n} Q_mx^m$.

Definir$k = m - n$. Tenemos:

Reclamo: Hay una biyección entre los caminos admisibles y los caminos de un$k\times (n + k)$cuadrícula ($k$horizontal,$n + k$segmentos verticales).

Prueba: Dado un camino admisible, le quitamos los siguientes segmentos: el$n$segmentos horizontales que siguen un punto de falla y el segmento vertical que sigue la primera vez que cruzamos (es decir, el primer segmento que está por encima de la diagonal). Concatenamos las piezas resultantes pegando sus extremos uno al siguiente. Observe 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, estos caminos de hecho están en la cuadrícula buscada.

Si tenemos uno de esos caminos$P$para leer el camino admisible correspondiente comenzamos poniendo un segmento horizontal y seguimos$P$hasta llegar a la diagonal principal, momento en el que ponemos otro segmento horizontal, y seguimos leyendo$P$. Ponemos segmentos horizontales hasta que hayamos tocado la diagonal$n$veces (sin contar el punto inicial). En ese momento ponemos un segmento vertical, y copiamos lo que queda de$P$. Al invertir los cálculos anteriores, vemos que este es de hecho un camino en una cuadrícula de$m\times m + 1$.

Fíjate que debido a que nuestro camino$P$Sube$n + k$veces siempre debemos poder empujarlo horizontalmente (forzarlo a fallar), contando el primer segmento desde la esquina inferior izquierda, n veces desde entonces, en el peor de los casos (k = 0) después de empujar las n veces que conseguimos tenemos movido$n + k$en ambas direcciones y todavía tenemos espacio extra para empujar hacia arriba una vez más. Esto prueba que el camino construido desde$P$sí es admisible. Esto concluye demostrando que esta correspondencia es en realidad una biyección.$\blacksquare$

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

[Los bordes amarillos son los que agregamos para asegurarnos de que falla hasta que queremos que tenga éxito]

Hemos probado 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 primeros principios. Hay$n + 1$eventos independientes que ocurren: lo que sucede antes de la primera falla, entre la primera y la segunda falla, hasta lo que sucede entre la$n - 1$el fracaso y el momento del éxito y luego lo que sucede después de que cruzamos la diagonal y subimos 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 horizontal y vertical, ya que no debemos cruzar la subdiagonal hasta el momento adecuado. Note que esto es importante, ya que si solo consideramos el$i\times i$cuadrado, en cambio, podríamos tener fallas intermedias entre los puntos finales, ya que las rutas catalanas pueden tocar la diagonal del cuadrado en el que viven, y no queremos esas fallas 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 de la contribución a la longitud horizontal!). Tenemos$n$de estos.

Luego, después de que se hace el último cuadrado catalán, tenemos un segmento vertical forzado y luego lo que queramos siempre que suceda 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 rejilla cuadrada y la franja vertical quita el$+1$, entonces 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*}$$ Hemos probado así 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*}$$ Usando lo que sabemos $$\displaystyle\sum_{i = 0}C_ix^i = \dfrac{1 - \sqrt{1 - 4x}}{2x}$$ y, 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 cancelando el factor $x^n$en ambos lados obtenemos la igualdad deseada.

Aquí hay un enfoque basado en el teorema de inversión de Lagrange . Seguimos el artículo Lagrange Inversion: when and how de R. Sprugnoli et al.

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 papel. La fórmula (G6) dice que si hay funciones $A(u)$y $\phi(u)$, de modo 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{blue}{F(x)}&\color{blue}{=\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{blue}{=\frac{1}{\sqrt{1-4x}}\left(\frac{1-\sqrt{1-4x}}{2x}\right)^n}\tag{7} \end{align*}$$ y sigue la demanda.

Comentario:

• En (2) usamos el coeficiente del 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) usamos 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 tome la solución con el signo menos, ya que ésta se puede expandir como función generadora.

• En (7) hacemos de nuevo algunas simplificaciones para obtener la forma deseada.