Una identidad que implican Coeficientes binomiales

Question

Demostrar la siguiente identidad $$\displaystyle \sum_{i+j=m}\frac{(n-1) \binom{ai+n-1}{i} \binom{aj+1}{j}}{(ai+n-1)(aj+1)} = \frac{n\binom{am+n}{m}}{am+n}$$ donde $i = 0,1,\cdots,m$ $m, n$ son enteros positivos y $a$ es un número entero positivo o incluso una fracción.

Una evidencia completa se puede encontrar en el famoso libro "Concreto de las Matemáticas" por Ronald L. Graham, Donald E. Knuth, y Oren Patashnik que es ampliamente utilizado como libro de texto en muchos departamentos de computación.

Otra evidencia completa se puede encontrar en el libro escrito por Egorychev que es directamente a través de la inversión de la regla de residuos, véase la página 49 del libro "representación Integral y el cálculo de la combinatoria sumas". Si usted está leyendo ese libro, tenga en cuenta que el índice de bajo $\sum$ puede extenderse hasta el infinito, porque el contorno de la integral no tiene ningún polo al $k>n$.

Answer 1

Este es un buen ejemplo para aplicar la inversión de la regla de poder formal de la serie declaró como regla 4 G. P. Egorychevs Integral de las Representaciones y el Cálculo de la Combinatoria Sumas la sección 1.2.2.

Creo que vale la pena presentar una prueba. Aquí se utiliza el coeficiente de operador $[z^n]$ para denotar el coeficiente de $z^n$ en un poder formal de la serie. Nos muestran

El siguiente es válido para $m,n\geq 1$ $a\in\mathbb{R}$ adecuado \begin{align*} \sum_{{i+j=m}\atop{i,j\geq 0}}&\frac{n-1}{ai+n-1}\binom{ai+n-1}{i}\frac{1}{aj+1}\binom{aj+1}{j} =\frac{1}{am+n}\binom{am+n}{m} \end{align*}

$$ $$

Obtenemos \begin{align*} \sum_{{i+j=m}\atop{i,j\geq 0}}&\frac{n-1}{ai+n-1}\binom{ai+n-1}{i}\frac{1}{aj+1}\binom{aj+1}{j}\\ &=\sum_{i=0}^m\frac{n-1}{ai+n-1}\binom{ai+n-1}{i}\frac{1}{am-ai+1}\binom{am-ai+1}{m-i}\\ &=\sum_{i=0}^\infty\left\{\binom{ai+n-1}{i}-a\binom{ai+n-2}{i-1}\right\}\\ &\qquad\qquad\cdot\left\{\binom{am-ai+1}{m-i}-a\binom{am-ai}{m-i-1}\right\}\tag{1}\\ &=\sum_{i=0}^{\infty}\left([z^i](1+z)^{ai+n-1}-a[z^{i-1}](1+z)^{ai+n-2}\right)\\ &\qquad\qquad\cdot\left([w^{m-i}](1+w)^{a(m-i)+1}-a[w^{m-i-1}](1+w)^{a(m-i)}\right)\\ &=[w^m](1+w)^{am}(1+w-aw)\\ &\qquad\qquad\cdot\sum_{i=0}^{\infty}\left(\frac{w}{(1+w)^a}\right)^i[z^i](1+z)^{n-2}(1+z-az)(1+z)^{ai}\tag{2}\\ &=[w^m](1+w)^{am}(1+w-aw)\left.\left((1+z)^{n-1}\right)\right|_{z=w}\tag{3}\\ &=[w^m](1+w)^{am+n}-a[w^{m-1}](1+w)^{am+n-1}\\ &=\binom{am+n}{m}-a\binom{am+n-1}{m-1}\\ &=\frac{1}{am+n}\binom{am+n}{m} \end{align*} y el reclamo de la siguiente manera.

Comentario:

• En (1) utilizamos la identidad $$\frac{q}{pk+q}\binom{pk+q}{k}=\binom{pk+q}{k}-p\binom{pk+q-1}{k-1}$$ We also set the upper limit of the sum to $\infty$ sin cambiar nada ya que son sólo la adición de cero.

• En (2) nos reorganizar la suma, el uso de la linealidad del coeficiente de operador y la regla de $[z^{n-k}]A(z)=[z^n]z^kA(z)$.

• En (3) se utiliza la inversión de la regla

\begin{align*} \sum_{i=0}^\infty w^i [z^i]A(z)f^i(z)=\left.\left(A(z)\frac{f(z)}{f(z)-zf^{\prime}(z)}\right)\right|_{z=g(w)} \end{align*} con $g(w)$ el inverso de a $w=\frac{z}{g(z)}$. Podemos obtener a partir de (2) \begin{align*} A(z)&=(1+z)^{n-2}(1+z-az)\\ f(z)&=(1+z)^a \end{align*} y obtener \begin{align*} A(z)\frac{f(z)}{f(z)-zf^{\prime}(z)}&=(1+z)^{n-2}(1+z-az)\frac{(1+z)^a}{(1+z)^a-az(a+z)^{a-1}}\\ &=(1+z)^{n-1} \end{align*} Desde $w=\frac{z}{f(z)}=\frac{z}{(1+z)^a}$ aplicamos en (3) la sustitución de $z=w$.

Answer 2

Lo que sigue es sólo una respuesta parcial.

Supongamos que buscamos para comprobar que

$$\sum_{q=0}^m \frac{1}{aq+n-1} \frac{1}{am+1-aq} {aq+n-1\elegir q} {am+1-aq\elegir m-q} \\ = \frac{n}{n-1} \frac{1}{am+n} {am+n\elegir m}.$$

Ahora observar que $$\frac{1}{aq+n-1} \frac{1}{am+1-aq} = \frac{1}{am+n} \frac{1}{aq+n-1} + \frac{1}{am+n} \frac{1}{am+1-aq}.$$

La identidad se convierte ahora en el

$$\sum_{q=0}^m \frac{1}{aq+n-1} {aq+n-1\elegir q} {am+1-aq\elegir m-q} \\ + \sum_{q=0}^m \frac{1}{am+1-aq} {aq+n-1\elegir q} {am+1-aq\elegir m-q} \\ = \frac{n}{n-1} {am+n\elegir m}.$$

Llamar a las dos piezas que aparecen aquí $S_1$ $S_2$ e iniciar con $S_1.$ Ahora tenemos

$${aq+n-1\choose q} = \frac{aq+n-1}{q} {aq+n-2\choose q-1}$$

así que $${aq+n-1\elegir q} - {aq+n-2\elegir q-1} = \frac{n-1}{q} {aq+n-2\elegir q-1} \\ = \frac{n-1}{aq+n-1} {aq+n-1\elegir q}.$$

Sustituyendo esto en $S_1$ rendimientos

$$\frac{1}{n-1} \sum_{q=0}^m {aq+n-1\elegir q} {am+1-aq\elegir m-q} \ \ - \frac{1}{n-1} \sum_{q=0}^m {aq+n-2\elegir q-1} {am+1-aq\elegir m-q}.$$

Hay dos piezas aquí llamarlos $T_{11}$ $T_{12}.$

Para $T_{11}$ introducir las integrales $${aq+n-1\elegir q} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{aq+n-1}}{z^{q+1}} \; dz$$

y

$${am+1-aq\elegir m-q} = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{am+1-aq}}{w^{m-p+1}} \; dw$$

El segundo de estos controles el rango lo podemos extender $q$ a el infinito para obtener

$$\frac{1}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{am+1}}{w^{m+1}} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n-1}}{z} \sum_{q\ge 0} \frac{w^p}{z^p} \frac{(1+z)^{aq}}{(1+w)^{aq}} \; dz\; dw \\ = \frac{1}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{am+1}}{w^{m+1}} \\ \times \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n-1}}{z} \frac{1}{1-w(1+z)^a/z/(1+w)^a} \; dz\; dw \\ = \frac{1}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{soy+un+1}}{w^{m+1}} \\ \times \frac{1}{2\pi i} \int_{|z|=\epsilon} (1+z)^{n-1} \frac{1}{(1+w)^az-w(1+z)^a} \; dz\; ps.$$

Esta respuesta no sea parcial que ahora restringir a $a=2$ y obtener

$$\frac{1}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{2m+3}}{w^{m+1}} \frac{1}{2\pi i} \int_{|z|=\epsilon} (1+z)^{n-1} \frac{1}{(z-w)(1-wz)} \; dz\; ps.$$

El polo en $z=w$ es el único en el interior del contorno y obtenemos

$$\frac{1}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{2m+n+2}}{w^{m+1}} \frac{1}{1-w^2} \; dw \\ = \frac{1}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{2m+n+1}}{w^{m+1}} \frac{1}{1-w} \; ps.$$

Para la pieza de la $T_{12}$ seguimos el mismo procedimiento y obtener

$$-\frac{a}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{2m+3}}{w^{m+1}} \frac{1}{2\pi i} \int_{|z|=\epsilon} (1+z)^{n-2} \frac{z}{(z-w)(1-wz)} \; dz\; dw$$

que los rendimientos de

$$-\frac{a}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{2m+n+1}}{w^{m}} \frac{1}{1-w^2} \; dw \\ = -\frac{a}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{2m+n}}{w^{m}} \frac{1}{1-w} \; ps.$$

La adición de las dos piezas que obtengamos para $S_1$

$$\frac{1}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{2m+n}}{w^{m}} \frac{1}{1-w} \left(\frac{1+w}{w} -2\right) \; dw \\ = \frac{1}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{2m+n}}{w^{m}} \frac{1}{1-w} \frac{1-w}{w}\; dw \\ = \frac{1}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{2m+n}}{w^{m+1}} \; dw = \frac{1}{n-1} {2m+n\elegir m}.$$

Volviendo a $S_2$ observa que

$${am+1-aq\elegir m-q} = \frac{am+1-aq}{m-q} {am-aq\elegir m-q-1}$$

así que $${am+1-aq\elegir m-q} - {am-aq\elegir m-q-1} = \frac{1}{m-q} {am-aq\elegir m-q-1} \\ = \frac{1}{am+1-aq} {am+1-aq\elegir q}.$$

Sustituyendo esto en $S_2$ rendimientos

$$\sum_{q=0}^m {aq+n-1\elegir q} {am+1-aq\elegir m-q} - \sum_{q=0}^m {aq+n-1\elegir q} {am-aq\elegir m-p-1}.$$

Llamar a estos dos pedazos $T_{21}$ $T_{22}.$ Reconocemos la pieza de la $T_{21}$ que es la misma que la pieza de la $T_{11}$ y obtenemos

$$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{2m+n+1}}{w^{m+1}} \frac{1}{1-w} \; ps.$$

Para la pieza de la $T_{22}$ obtenemos

$$- \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{2m+2}}{w^{m}} \frac{1}{2\pi i} \int_{|z|=\epsilon} (1+z)^{n-1} \frac{1}{(z-w)(1-wz)} \; dz\; ps.$$

El polo en $z=w$ rendimientos

$$- \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{2m+n+1}}{w^{m}} \frac{1}{1-w^2} \; dw \ \ = - \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{2m+n}}{w^{m}} \frac{1}{1-w} \; dw$$

Este es el mismo como la pieza de la $T_{12}$ y por lo tanto obtenemos para $S_2$ cuando la adición de $T_{21}$ $T_{22}$ la contribución

$${2m+n\choose m}$$

para una respuesta final de $$\left(1+\frac{1}{n-1}\right) {2m+n\elegir m} = \frac{n}{n-1} {2m+n\elegir m}.$$

Adenda. En realidad podemos resolver esto para todos los valores enteros de $a$ y no sólo para $a=2.$ Recordar la integral para $T_{11}$ donde estamos decidió crear instancias de $a$ para el valor de $2:$

$$\frac{1}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{soy+un+1}}{w^{m+1}} \\ \times \frac{1}{2\pi i} \int_{|z|=\epsilon} (1+z)^{n-1} \frac{1}{(1+w)^az-w(1+z)^a} \; dz\; ps.$$

Supongamos que podemos demostrar que $z=w$ es el único polo en el interior del contorno y es simple. Tenemos

$$\left((1+w)^z - w(1+z)^a\right)' = (1+w)^a - aw(1+z)^{- 1}.$$

Sustituyendo esto en el exterior integral de los rendimientos

$$\frac{1}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{soy+un+1}}{w^{m+1}} (1+w)^{n-1} \frac{1}{(1+w)^{- 1}} \frac{1}{1+w-aw}\; dw \\ = \frac{1}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{am+n+1}}{w^{m+1}} \frac{1}{1+w-aw}\; ps.$$

Para la pieza de la $T_{21}$ tenemos $$- \frac{1}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{soy+un+1}}{w^{m+1}} (1+w)^{n-2} \frac{w}{(1+w)^{- 1}} \frac{1}{1+w-aw}\; dw \ \ = - \frac{1}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{am+n}}{w^{m}} \frac{1}{1+w-aw}\; ps.$$

La adición de las dos piezas de los rendimientos

$$\frac{1}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{am+n}}{w^{m}} \left(\frac{1+w}{w} - \right) \frac{1}{1+w-aw}\; dw \\ = \frac{1}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{am+n}}{w^{m+1}} (1+w-aw) \frac{1}{1+w-aw}\; dw \\ = \frac{1}{n-1} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{am+n}}{w^{m+1}} \; dw = \frac{1}{n-1} {am+n\elegir m}.$$

Este es precisamente el resultado deseado y las piezas $T_{21}$ y $T_{22}$ ir a través del mismo modo, QED.

Answer 3

Aquí es una respuesta a la segunda suma que se publicó, que de hecho usan exactamente el mismo método que el primer y ser más compactos, fáciles de leer y entender.

Supongamos que buscamos para comprobar que

$$\sum_{k=0}^m \frac{q}{pk+q} {pk+q\elegir k} {pm-pk\elegir m-k} = {mp+q\elegir m}.$$

Observar que

$${pk+q\choose k} = \frac{pk+q}{k} {pk+q-1\choose k-1}$$

así que $${pk+q\elegir k} - p {pk+q-1\elegir k-1} = \frac{q}{k} {pk+q-1\elegir k-1} = \frac{q}{pk+q} {pk+q\elegir k}.$$

Esto produce dos piezas para la suma, llame a $S_1$

$$\sum_{k=0}^m {pk+q\choose k} {pm-pk\choose m-k}$$

y $S_2$

$$- p \sum_{k=0}^m {pk+q-1\choose k-1} {pm-pk\choose m-k}.$$

Para $S_1$ introducir las integrales

$${pk+q\elegir k} = \frac{1}{2\pi i} \int_{|z|=\gamma} \frac{(1+z)^{pk+p}}{z^{k+1}} \; dz$$

y

$${pm-pk\elegir m-k} = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{pm-pk}}{w^{m-k+1}} \; ps.$$

El segundo controla el rango de la suma debido a que el polo a cero se desvanece al$k\gt m$, por lo que podemos extender $k$ hasta el infinito, para la suma

$$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{pm}}{w^{m+1}} \frac{1}{2\pi i} \int_{|z|=\gamma} \frac{(1+z)^{p}}{z} \sum_{k\ge 0} \frac{w^k}{z^k} \frac{(1+z)^{pk}}{(1+w)^{pk}} \; dz\; dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{pm}}{w^{m+1}} \frac{1}{2\pi i} \int_{|z|=\gamma} \frac{(1+z)^{p}}{z} \frac{1}{1-w(1+z)^p/z/(1+w)^p} \; dz\; dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{pm+p}}{w^{m+1}} \frac{1}{2\pi i} \int_{|z|=\gamma} (1+z)^{q} \frac{1}{z(1+w)^p-w(1+z)^p} \; dz\; ps.$$

Supongamos $|\epsilon| < |\gamma|$ que hace $\left|\frac{w(1+z)^p}{z(1+w)^p}\right| < 1$ , de modo que hemos de convergencia de la serie geométrica y supongamos que se puede demostrar que $z=w$ es el único polo en el interior del contorno y es simple. Tenemos

$$\left((1+w)^p z - w(1+z)^p\right)' = (1+w)^p - pw(1+z)^{p-1} = (1+w)^{p-1}(1+w-wp).$$

Podemos optar $|\epsilon|$ lo suficientemente pequeño tal que $|1+w-wp| >0$, por lo que el polo es de orden 1, lo que produce

$$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{pm+p}}{w^{m+1}} (1+w)^q \frac{1}{(1+w)^{p-1}} \frac{1}{1+w)-mp} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{pm+q+1}}{w^{m+1}} \frac{1}{1+w)-mp} \; ps.$$

Siguiendo exactamente el mismo procedimiento que obtengamos para $S_2$

$$-p \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{pm+q}}{w^{m}} \frac{1}{1+w)-mp} \; ps.$$

La adición de estas dos piezas ahora rendimientos

$$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{pm+q}}{w^{m}} \left(\frac{1+w}{w} - p\right) \frac{1}{1+w)-mp} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{pm+q}}{w^{m+1}} \; dw \\ = {pm+q\elegir m}.$$

Comentario Lunes 25 De Enero De 2016.

Una alternativa de la prueba que es totalmente riguroso y no depende de suposiciones acerca de los polos de un bivariante función compleja procede a partir de la integral

$$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{pm}}{w^{m+1}} \sum_{k\ge 0} \frac{w^k}{(1+w)^{pk}} \frac{1}{2\pi i} \int_{|z|=\gamma} \frac{(1+z)^{p}}{z^{k+1}} (1+z)^{pk} \; dz\; dw$$

Ahora ponga

$$u = \frac{z}{(1+z)^p} \quad\text{e introducir}\quad g(u) = z.$$

Entonces tenemos $$du = \left(\frac{1}{(1+z)^p} - p\frac{z}{(1+z)^{p+1}}\right) \; dz = \left(\frac{u}{g(u)} - \frac{pu}{1+g(u)}\right) \; dz$$

y $$dz = \frac{1}{u}\frac{g(u) (1+g(u))}{1 + g(u) - p g(u)} \; du.$$

Este rendimientos

$$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{pm}}{w^{m+1}} \sum_{k\ge 0} \frac{w^k}{(1+w)^{pk}} \\ \times \frac{1}{2\pi i} \int_{|u|=\gamma} \frac{1}{g(u) u^{k}} (1+g(u))^q \frac{1}{u}\frac{g(u) (1+g(u))}{1 + g(u) - p g(u)} \; du\; dw$$

o $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{pm}}{w^{m+1}} \a la izquierda.(1+g(u))^q \frac{1+g(u)}{1 + g(u) - p g(u)} \right|_{u=w/(1+w)^p} \; ps.$$

Ahora observe que el$g(w/(1+w)^p) = w$, por definición, así que tenemos

$$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{pm}}{w^{m+1}} (1+w)^q \frac{1+w}{1 + w p w} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{pm+q+1}}{w^{m+1}} \frac{1}{1 + w p w} \; ps.$$

Este es exactamente el mismo que antes, y el resto de la prueba continúa sin cambios.

Lo hemos utilizado aquí es la técnica de la aniquilado coeficiente de extractores de que hay varios ejemplos en este MSE enlace Yo y en este MSE enlace II y también aquí en este MSE enlace III.

Answer 4

Seguir el mismo razonamiento de demostrar esta identidad, $$\displaystyle \sum_{i=0}^m\frac{q }{pi+q}\binom{pi+q}{i} \binom{pm-pi}{m-i} = \binom{mp+q}{m}$$ Puedes leer el libro sí mismo. Demasiado difícil para publicar el libro aquí!

puede ser demostrado mediante la inversión de la regla de residuos, véase la página 49 representación Integral y el cálculo de sumas de combinatoria