¿Cuál es la suma de esta secuencia finita?

Question

$$\ sum \ limits_ {t = 0} ^ {n - m} {\ left ({\begin{array}{*{20}{c}} {t + k}\\ t \end {array}} \ right)} \ left ({\begin{array}{*{20}{c}} {n - k - t}\\ {n - m - t} \end {array}} \ right )$$ $k$,$n$,$m$ son constantes y$k <= m <= n$. ¿Alguna solución de forma cerrada?

Es un problema de mi libro de texto. Es tan raro. Lo he pensado durante toda la noche y todavía no puedo encontrar la respuesta :(

Answer 1

La clave es reconocer la expresión dada como la convolución de dos más simple de la serie. El uso de la conocida generación de función $$\sum_{j=0}^\infty \binom{j+q}j x^j = (1-x)^{-q-1},$$ vemos que $$\begin{align*} \sum_{j=0}^\infty x^j \sum_{t=0}^j \binom{t+k}t \binom{j-t-(k-m)}{j-t} &= \sum_{j=0}^\infty \sum_{t=0}^j \binom{t+k}t x^t \binom{j-t-(k-m)}{j-t} x^{j-t} \\ &= \sum_{t=0}^\infty \binom{t+k}t x^t \sum_{j=t}^\infty \binom{j-t-(k-m)}{j-t} x^{j-t} \\ &= \sum_{t=0}^\infty \binom{t+k}t x^t \sum_{i=0}^\infty \binom{i-(k-m)}i x^i \\ &= (1-x)^{-k-1} (1-x)^{k-m-1} = (1-x)^{-m-2}. \end{align*}$$ Desde $(1-x)^{-m-2} = \sum_{j=0}^\infty \binom{j+m+1}j x^j$, que han derivado la identidad $$\sum_{j=0}^\infty x^j \sum_{t=0}^j \binom{t+k}t \binom{j-t-(k-m)}{j-t} = \sum_{j=0}^\infty \binom{j+m+1}j x^j;$$ Tomando los coeficientes de $x^{n-m}$ en ambos lados da $$\sum_{t=0}^{n-m} \binom{t+k}t \binom{n-t-k}{n-m-t} = \binom{n+1}{n-m} = \binom{n+1}{m+1}.$$

Answer 2

Esta es una pregunta interesante.

Usando la parte superior negación, la aplicación de la Vandermonde identidad, usando la parte superior negación de nuevo y la aplicación de la simetría da lo siguiente:

$$\begin{align} \sum_{t=0}^{n-m}{\color{red}t+k\choose \color{red}t}{n-k-\color{red}t\choose n-m-\color{red}t}&=\sum_{t=0}^{n-m}{-k-1\choose \color{red}t}{k-m-1\choose n-m-\color{red}t}(-1)^{t+(n-m-t)}\\ &=(-1)^{n-m}{-m-2\choose n-m}\\ &=(-1)^{(n-m)+(n-m)}{n+2-1\choose n-m}\\ &={n+1\choose {n-m}}\\ &={n+1\choose {m+1}}\qquad \blacksquare \end{align}$$

Más información acerca de la parte superior de la negación y la Vandermonde identidad aquí:

https://proofwiki.org/wiki/Negated_Upper_Index_of_Binomial_Coefficient http://en.wikipedia.org/wiki/Vandermonde%27s_identity

Answer 3

Hay una manera bastante fácil de combinatoria prueba. Contamos el número de subconjuntos de a $\{0,1,\ldots,n\}$ del tamaño de la $m+1$ en dos maneras. En primer lugar, por supuesto, hay $\binom{n+1}{m+1}$ de ellos. Ahora supongamos que $S=\{a_0,\ldots,a_m\}$ es un subconjunto, donde $a_0<\ldots<a_m$. Claramente $a_k\ge k$; deje $t=a_k-k\ge 0$. Por otra parte,

$$n\ge m\ge a_k+(m-k)=m+t\;,$$

por lo $t\le n-m$. Para un determinado $t\in\{0,\ldots,n-m\}$ hay

$$\binom{a_k}k=\binom{t+k}k=\binom{t+k}t$$

las formas para elegir el $k$ de los miembros de $S$ bajo $a_k=t+k$ y

$$\binom{n-(t+k)}{m-k}=\binom{n-k-t}{n-m-t}$$

las formas para elegir el $m-k$ de los miembros de $S$ sobre $a_k=t+k$. Por lo tanto, hay

$$\binom{t+k}t\binom{n-k-t}{n-m-t}$$

formas de elegir los $S$ $a_k=t+k$ y en total

$$\sum_{t=0}^{n-m}\binom{t+k}t\binom{n-k-t}{n-m-t}$$

formas de elegir los $S$. De ello se sigue que

$$\sum_{t=0}^{n-m}\binom{t+k}t\binom{n-k-t}{n-m-t}=\binom{n+1}{m+1}\;.$$

Answer 4

Por medio de enriquecimiento aquí es otra prueba de álgebra básica variables complejas.

Buscamos para calcular $$\sum_{t=0}^{n-m} {t+k\choose t} {n-k-t\choose n-m-t}.$$

Introducir la representación integral $${n-k-t\elegir n-m-t} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n-k-t}}{z^{n-m-t+1}} \; dz.$$

Usamos esto para obtener una integral para la suma. Tenga en cuenta que cuando se $t>n-m$ tenemos $1>n-m-t+1$, lo que significa que la integral es cero (en todo el de la función). Por lo tanto, podemos extender la suma de los infinitos términos, llegar $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n-k}}{z^{n-m+1}} \sum_{t\ge 0} {t+k\c} \frac{z^t}{(1+z)^t}\; dz.$$

Esto se simplifica a $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n-k}}{z^{n-m+1}} \frac{1}{(1-z/(1+z))^{k+1}} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n-k}}{z^{n-m+1}} \frac{(1+z)^{k+1}}{(1+z-z)^{k+1}} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n+1}}{z^{n-m+1}} \; dz.$$

Esta integral se evalúa a través de una inspección a $${n+1\choose n-m} = {n+1 \choose m+1}.$$

Al parecer, este método es debido a Egorychev.