Una simple combinatoria suma finita que encontré, que parece funcionar, habría buenas razones para trabajar, pero puedo ' t encontrar en la literatura.

Question

Yo estaba haciendo una verificación de consistencia para algunos cálculos que estoy realizando para mi tesis de maestría (aproximadamente - acerca de un problema en discretos modelo bayesiano de selección) y resulta que mi elección de los priores sólo es consistente si esta identidad es verdadera:

$$\sum_{k=0}^{N}\left[ \binom{k+j}{j}\binom{N-k+j}{j}\right] = \binom{N+2j+1}{2j+1}$$

Ahora, esto parece que funciona para números pequeños, pero he buscado mucho en la literatura y no la puedo encontrar.(Tengo una formación en la física, así que probablemente mi conocimiento de "literatura" es el problema aquí). Ni yo puedo demostrar! Tiene alguno de ustedes visto esto antes? Este puede ser reescrito de forma equivalente, en algunos de los más comúnmente visto? Puede ser demostrado a la derecha...o mal? Gracias de antemano! :)

Answer 1

Su identidad es correcta. No sé de referencia de improviso, pero aquí es una prueba.

El lado derecho, $\binom{N+2j+1}{2j+1}$, es el número de bitstrings de longitud $N+2j+1$ consta de $N$ ceros y $2j+1$ .

La suma de la izquierda cuenta el mismo conjunto de bitstrings. Es decir, para $0\le k\le N$, el término $\binom{k+j}j\binom{N-k+j}j$ es el número de los bitstrings en el que la media, con $j$ queridos en cualquier lado, es en el $k+j+1^\text{st}$ posición; es decir, se ha $k$ ceros y $j$ a la izquierda, $N-k$ ceros y $j$ a la derecha.

P. S. he encontrado su identidad en László Lovász, Problemas de Combinatoria y Ejercicios, North-Holland, 1979 (primera edición), donde es el Ejercicio 1.42(i) en la p. 18, con la sugerencia de la página. 96 de la solución y en la p. 172. Lovász da la identidad en la siguiente (más general): $$\sum_{k=0}^m\binom{u+k}k\binom{v-k}{m-k}=\binom{u+v+1}m.$$ Si establecemos $m=N$, $u=j$, $v=N+j$, esto se convierte en $$\sum_{k=0}^N\binom{j+k}k\binom{N+j-k}{N-k}=\binom{N+2j+1}N$$ que es claramente equivalente a su identidad $$\sum_{k=0}^N\binom{k+j}j\binom{N-k+j}j=\binom{N+2j+1}{2j+1}.$$

Answer 2

Tenemos

$$\sum_{k=0}^N {k+j\elegir j} {N-k+j\elegir j} = \sum_{k=0}^N {k+j\elegir j} {N-k+j\elegir N-k} \\ = \sum_{k=0}^N {k+j\elegir j} [z^{N-k}] (1+z)^{N-k+j} = [z^N] (1+z)^{N+j} \sum_{k=0}^N {k+j\elegir j} z^k (1+z)^{-k}.$$

Ahora podemos extender $k$ más allá de $N$ ya que no hay contribución a la $[z^N]$ en la parte delantera en este caso (tenemos $z^k (1+z)^{-k} = z^k +\cdots$)

$$[z^N] (1+z)^{N+j} \sum_{k\ge 0} {k+j\elegir j} z^k (1+z)^{-k} = [z^N] (1+z)^{N+j} \frac{1}{(1-z/(1+z))^{j+1}} \\ = [z^N] (1+z)^{N+j} \frac{(1+z)^{j+1}}{(1+z-z)^{j+1}} = [z^N] (1+z)^{N+2j+1} = {N+2j+1\elegir 2j+1}.$$