¿Cómo puedo probar que
$$\sum_{0 \le k \le t} {t-k \choose r}{k \choose s}={t+1 \choose r+s+1} \>?$$
Esto lo vi en un libro de discutir la generación de funciones.
Respuestas
¿Demasiados anuncios?
freespace
Puntos
9024
Vamos $r$, $t$, $s$ ser fijo.
$\binom{t+1}{r+s+1}$ = número de posibilidades ¿cómo puedo elegir el $r+s+1$ elementos de $\{1,2,\dots,t+1\}$
Vamos a pedir los elementos elegidos cada vez más: $a_1 < a_2 < \dots < a_{r+s+1}$
¿Cuál es el número de posibilidades donde $a_{s+1}=k+1$? Tenemos que elegir a $s$ elementos de $\{1,2,\dots,k\}$ y el restante $r$ elementos de $\{k+2,\dots,t+1\}$. Tenemos $$\binom ks \cdot \binom {t-k}r$$ posibilidades.
La última expresión es distinto de cero sólo para$k\ge 0$$t-k\ge 0$, lo que nos da el rango de la suma.
Aunque probablemente no estás interesado en una combinatoria de la prueba, ya que se menciona explícitamente la generación de funciones.
Voy a hacer más explícito el momento creo Phira está haciendo. La identidad es Vandermonde de la convolución además de la parte superior de la negación de la regla de los coeficientes binomiales.
La parte superior de la negación de la regla de los coeficientes binomiales es $$\binom{n}{k} = (-1)^k \binom{k-n-1}{k},$$ which holds when $k$ es un número entero (véase, por ejemplo, el Concreto de las Matemáticas, 2ª edición, pág. 164). La aplicación de este, obtenemos $$\sum_{0 \le k \le t} {t-k \choose r}{k \choose s} = \sum_{0 \le k \le t} {t-k \choose t-k-r}{k \choose k-s}= \sum_{0 \le k \le t} (-1)^{t-k-r}{-r-1 \choose t-r-k} (-1)^{k-s}{-s-1 \choose k-s}$$ $$ = (-1)^{t-r-s}\sum_{0 \le k \le t}{-r-1 \choose t-r-k}{-s-1 \choose -s+k}.$$ Ahora, el uso de Vandermonde de la convolución (o, más generalmente, el Chu-Vandermonde de identidad), para obtener $$ = (-1)^{t-r-s}{-r-s-2 \choose t-r-s},$$ y, a continuación, aplicar la parte superior de la negación de la regla de nuevo, que nos da lo que queremos: $$={t+1 \choose t-r-s} = {t+1 \choose r+s+1}.$$
Heng-Cheong Leong
Puntos
529
Este enfoque se basa en la generación de función.
Por http://math.arizona.edu/~faris/combinatoricsweb/generar.pdf
Sabemos que $\sum \limits_{n=0}^{\infty} {n \choose k} y^n= \frac{y^k}{(1-y)^{k+1}} $
$x \cdot \sum \limits_{l=0}^{\infty} {l \elegir r} x^l \cdot \sum \limits_{k=0}^{\infty} {k \elegir s} x^k = x \cdot \frac{x^r}{(1-x)^{i+1}} \cdot \frac{x^s}{(1-x)^{s+1}} =\frac{x^{r+s+1}}{(1-x)^{r+s+2}} = \sum \limits_{n=0} {n \elegir r+s+1} x^n$
El coeficiente de $x^{t+1}$ de la $x \cdot \sum \limits_{l=0}^{\infty} {l \choose r} x^l \cdot \sum \limits_{k=0}^{\infty} {k \choose s} x^k $ $\sum \limits_{l+k=t} {l \choose r}{k \choose s}$
Deje $n=t+1$, ${t+1 \choose r+s+1} = \sum \limits_{l+k=t} {l \choose r}{k \choose s} = \sum \limits_{0 \le k \le t} {t-k \choose r}{k \choose s}$
Tas
Puntos
11
Tenga en cuenta que esta suma es Vandermonde de la identidad.
Calcular en ambas sumas la relación de consecutivos sumandos y comparar entre ellos. Verás que después de un cambio de variables, que son el mismo.
Por lo tanto, la suma de dos sólo difieren por un factor en cada término y el resultado.
Si quieres saber más sobre esto, lea acerca de las funciones hipergeométricas.
