¿Es esta identidad combinatoria un caso especial del teroema de Saalschutz?

Question

Cuando resolví una pregunta, se utilizó la siguiente identidad combinatoria $$ \sum_{k=0}^{n}(-1)^k{n\choose k}{n+k\choose k}{k\choose j}=(-1)^n{n\choose j}{n+j\choose j}. $$ Pero demostrar esta identidad es difícil para mí. Creo que puede ser un caso especial del teroema de Saalschutz, que se enuncia así $$ \sum_{k=0}^{n}\frac{(-n)_k(a)_k(b)_k}{(1)_k(c)_k(1+a+b-c-n)_k}=\frac{(c-a)_n(c-b)_n}{(c)_n(c-a-b)_n}, $$ donde $(a)_k=a\cdot (a+1)\cdots (a+k-1)$ . Si no es el caso especial del teroema de Saalschutz, ¿puede presentar una prueba de esta identidad? Todas las pistas, pruebas y referencias son bienvenidas.

Answer 1

Multiplica la identidad deseada por $(-1)^n$ para conseguir

$$\sum_{k=0}^{n}(-1)^{n-k}\binom{n}k\binom{n+k}k\binom{k}j=\binom{n}j\binom{n+j}j\;,$$

y reescribirlo como

$$\sum_{k=0}^n(-1)^k\binom{n}k\binom{2n-k}{n-k}\binom{n-k}j=\binom{n}j\binom{n+j}n\;.\tag{1}$$

Podemos suponer que $j\le n$ . Usted tiene $2n$ bolas blancas numeradas de $1$ a través de $2n$ . El lado derecho de $(1)$ es el número de formas de elegir $j$ de las bolas de las bolas con números $1$ a través de $n$ y los arroja en una caja con las bolas numeradas $n+1$ a través de $2n$ y, a continuación, elija $n$ de las bolas de la caja y pintarlas de rojo.

Como alternativa, hay $\binom{2n}n\binom{n}j$ formas de elegir cualquier $j$ de las bolas numeradas $1$ a través de $n$ , échalos en una caja con las bolas numeradas $n+1$ a través de $2n$ y, a continuación, elija cualquier $n$ de la $2n$ bolas para pintar de rojo, independientemente de que las bolas estén o no en la caja. Por supuesto, algunos de estos resultados dan lugar a bolas rojas no en la caja, y queremos excluirlos.

Para $k=1,\ldots,n$ dejar $B_k$ sea el conjunto de resultados en los que la bola $k$ termina en rojo pero no en la caja. Hay $\binom{2n-1}{n-1}$ formas de elegir el otro $n-1$ bolas rojas, y hay $\binom{n-1}j$ formas de elegir $j$ bolas de la primera $n$ , no incluido el balón $k$ para entrar en la caja. Así,

$$|B_k|=\binom{2n-1}{n-1}\binom{n-1}j\;.$$

Del mismo modo, si $1\le k<\ell\le n$ ,

$$|B_k\cap B_\ell|=\binom{2n-2}{n-2}\binom{n-2}j\;,$$

y en general para $1\le k_1<k_2<\ldots k_m\le n$ tenemos

$$\left|\bigcap_{\ell=1}^mB_{k_\ell}\right|=\binom{2n-m}{n-m}\binom{n-m}j\;,$$

y vemos que $(1)$ es sólo una aplicación del principio de inclusión-exclusión.

Answer 2

El resultado es más fácil de demostrar sin el uso del teorema de Saalschutz.

Un buen punto de partida para evaluar estas sumas puede ser escribirlas en términos de factoriales: $$ (-1)^k \binom{n}{k}\binom{n+k}{k}\binom{k}{j} =\frac{(-1)^k\,n!\,(n+k)!\,k!}{k!\,(n-k)!\,k!\,n!\,j!\,(k-j)!} =\frac{(-1)^k\,(n+k)!}{k!\,(n-k)!\,j!\,(k-j)!} $$ para $j\le k\le n$ (si no, el LHS es cero). A menudo pienso en la suma como sobre todo $k\in\mathbb{Z}$ pero con la convención de que $1/r!=0$ cuando $r$ es un número entero negativo.

Puede observar que $k$ aparece en cuatro de los factoriales. Esto significa que podemos intentar reescribir la expresión de manera que podamos utilizar la regla $$ \sum_k\binom{a}{p+k}\binom{b}{q-k}=\binom{a+b}{p+q} $$ donde $a$ o $b$ puede ser negativo utilizando la conversión $$ \binom{-(m+1)}{k} =(-1)^k\binom{m+k}{k} =(-1)^k\binom{m+k}{m}. $$ Podemos hacerlo como $$ \frac{(-1)^k\,(n+k)!}{k!\,(n-k)!\,j!\,(k-j)!} =(-1)^k\binom{n+k}{k}\binom{n-j}{n-k}\binom{n}{j} =\binom{-(n+1)}{k}\binom{n-j}{n-k}\binom{n}{j} $$ que nos da la suma $$ \sum_k\binom{-(n+1)}{k}\binom{n-j}{n-k}\binom{n}{j} =\binom{-(j+1)}{n}\binom{n}{j} =(-1)^n\binom{n+j}{j}\binom{n}{j}. $$

---

Como ha señalado Darij, el resultado podría obtenerse de forma un poco más directa (sin escribir todos los factoriales) utilizando $$ \binom{n}{k}\binom{k}{j}=\binom{n}{j}\binom{n-j}{n-k}. $$ Por supuesto, como nunca recuerdo este tipo de reglas, personalmente tengo que escribirlo como factoriales de todas formas, pero hacerlo sólo para estos dos binomios es un poco más sencillo que hacerlo para los tres (y más en casos más complicados).

Answer 3

El LHS es el coeficiente de $x^j$ en: $$ \sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{n+k}{k}(1+x)^k $$ de ahí que sólo tengamos que encontrar: $$ \sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{n+k}{k}z^k =\phantom{}_2 F_1(-n,1+n,1,z)=P_n^{(0,0)}(1-2z)$$ que es un polinomio de Jacobi, más conocido como el polinomio de Legendre desplazado $\tilde{P}_n(z)$ .

Entonces tu afirmación se desprende de la La fórmula de Rodrigues .

Answer 4

Observación. Incorpora una corrección de Markus Scheuer.

Supongamos que queremos evaluar

$$S_j(n) = \sum_{k=0}^n (-1)^k {n\choose k} {n+k\choose k} {k\choose j}$$

que se afirma que es $$(-1)^n {n\choose j}{n+j\choose j}.$$

Introduzca $${n+k\choose k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n+k}}{z^{k+1}} \; dz$$

y $${k\choose j} = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{k}}{w^{j+1}} \; dw.$$

Esto da como resultado para la suma $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n}}{z} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{j+1}} \sum_{k=0}^n (-1)^k {n\choose k} \frac{(1+z)^k (1+w)^k}{z^k} \; dw \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n}}{z} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{j+1}} \left(1-\frac{(1+w)(1+z)}{z}\right)^n \; dw \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n}}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{j+1}} \left(-1-w-wz\right)^n \; dw \; dz \\ = \frac{(-1)^n}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n}}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{j+1}} \left(1+w+wz\right)^n \; dw \; dz .$$

Esto es $$\frac{(-1)^n}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n}}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{j+1}} \sum_{q=0}^n {n\choose q} w^q (1+z)^q \; dw \; dz.$$

La extracción del residuo en $w=0$ obtenemos $$\frac{(-1)^n}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n}}{z^{n+1}} {n\choose j} (1+z)^j \; dz \\ = {n\choose j} \frac{(-1)^n}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n+j}}{z^{n+1}}\; dz \\ = (-1)^n {n\choose j} {n+j\choose n}.$$

probando así la afirmación.

Answer 5

He aquí otra variación del tema (similar a las técnicas presentadas en la respuesta de Marko Riedel).

Primero vamos a comprobar, si \begin{align*} \sum_{k=0}^{n}(-1)^k{n\choose k}{n+k\choose k}{k\choose j}=(-1)^n{n\choose j}{n+j\choose j}\tag{1} \end{align*} es un Identidad de Saalschütz .

Selon $A=B$ sección 3.5, el Identidad de Saalschütz tiene la representación general como la serie hipergeométrica \begin{align*} _{3}F_{2}\left(a,b,c;d,e;1\right)=\sum_{k=0}^{\infty}\frac{(a)_k(b)_k(c)_k}{(d)_k(e)_k} \end{align*} con $a+b+c+1=d+e$ y $c$ un número entero negativo.

Tenga en cuenta que $(x)_k=x(x-1)\cdot\ldots\cdot (x-k+1)$ es el _Símbolo del martillo pilón_ .

Desde \begin{align*} a_k&=(-1)^k\binom{n}{k}\binom{n+k}{k}\binom{k}{j}\\ &=(-1)^k\frac{(n+k)!}{k!(n-k)!(k-j)!j!} \end{align*} El cociente $\frac{a_{k+1}}{a_k}$ es \begin{align*} \frac{a_{k+1}}{a_k}=\frac{(k+1)^2(k+1-j)}{(k-n)(k+n+1)}\cdot\frac{1}{k+1} \end{align*} que da $$_{3}F_{2}\left(1,1,1-j;-n,n+1;1\right)$$ Observamos \begin{align*} a+b+c+1&=4-j\\ d+e&=1 \end{align*} y concluir que, si mi cálculo es correcto, la identidad binomial es una identidad de Saalschütz sólo en el caso $j=3$ .

Prueba de la identidad binomial

Utilizamos Egorychevs cálculo formal de residuos para series de potencia .

Nota: Esta poderosa técnica se basa en la Teorema del residuo de Cauchys y fue presentado por G.P. Egorychev ( Representación integral y cálculo de sumas combinatorias ) para calcular las identidades binomiales.

Sólo utilizamos dos aspectos de esta teoría:

Dejemos que $A(z)=\sum_{j=0}^{\infty}a_jz^j$ ser un serie de potencia formal entonces

• Escribe los coeficientes binomiales como residuos de los correspondientes serie de potencia formal

\begin{align*} \mathop{res}_{z}\frac{A(z)}{z^{j+1}}=a_j\tag{1} \end{align*}

• Aplicar el regla de sustitución para las series de potencia formales:

\begin{align*} A(z)=\sum_{j=0}^{\infty}a_jz^{j}=\sum_{j=0}^{\infty}z^j\mathop{res}_{w}\frac{A(w)}{w^{j+1}}\tag{2} \end{align*}

Observamos:

\begin{align*} \sum_{k=0}^{\infty}&(-1)^k{n\choose k}{n+k\choose k}{k\choose j}\tag{3}\\ &=\sum_{k=0}^{\infty}(-1)^k\mathop{res}_{z}\frac{(1+z)^n}{z^{k+1}} \mathop{res}_{u}\frac{(1+u)^{n+k}}{u^{k+1}} \mathop{res}_{t}\frac{(1+t)^{k}}{t^{j+1}}\tag{4}\\ &=\mathop{res}_{u,t}\frac{(1+u)^n}{ut^{j+1}}\sum_{k=0}^{\infty}\left((-1)\frac{(1+u)(1+t)}{u}\right)^k \mathop{res}_{z}\frac{(1+z)^n}{z^{k+1}}\tag{5}\\ &=\mathop{res}_{u,t}\frac{(1+u)^n}{ut^{j+1}}\left(1-\frac{(1+u)(1+t)}{u}\right)^n\tag{6}\\ &=(-1)^n\mathop{res}_{u,t}\frac{(1+u)^{n}}{u^{n+1}t^{j+1}}\left(1+(1+u)t\right)^n\\ &=(-1)^n\mathop{res}_{u}\frac{(1+u)^{n}}{u^{n+1}}[t^j]\sum_{k=0}^n\binom{n}{k}(1+u)^kt^k\tag{7}\\ &=(-1)^n\mathop{res}_{u}\frac{(1+u)^{n}}{u^{n+1}}\binom{n}{j}(1+u)^j\\ &=(-1)^n\binom{n}{j}\mathop{res}_{u}\frac{(1+u)^{n+j}}{u^{n+1}}\\ &=(-1)^n\binom{n}{j}\binom{n+j}{n} \end{align*}

Comentario:

• En (3) cambiamos el límite a $\infty$ sin cambiar el valor, ya que sólo añadimos $0$ .

• En (4) utilizamos $(1+z)^n$ como serie de potencia formal con los coeficientes $\binom{n}{k}$ según (1) y de forma similar para las expresiones en $u$ y $t$

• En (5) hacemos algunos reajustes para preparar la aplicación de la regla de sustitución

• En (6) aplicamos la regla de sustitución según (2)

• En (7) utilizamos el coeficiente de operador $[t^j]$ para denotar el coeficiente de $t_j$ en la suma. Obsérvese que lo siguiente es válido cuando se utiliza el operador residual formal $\mathop{res}$

$$\mathop{res}_t\frac{A(t)}{t^{j+1}}=[t^{-1}]t^{-j-1}A(t)=[t^j]A(t)$$