Cómo probar: $\sum_{k=m+1}^{n} (-1)^{k} \binom{n}{k}\binom{k-1}{m}= (-1)^{m+1}$

Question

Mostrar que si $m$ $n$ son enteros con $0\leq m<n$ $$\sum_{k=m+1}^{n} (-1)^{k} \binom{n}{k}\binom{k-1}{m}= (-1)^{m+1}$$

Intentos:

• $(-1)^{k}\binom{n}{k}$ es el coeficiente de $x^{k}$ en la expansión de $(1-x)^{n}$

• Y $\binom{k-1}{m}$ es el coeficiente de $x^{m}$ en la expansión de $(1+x)^{k-1}$.

Eso es todo lo que podría venir para arriba con.

Answer 1

Siguiendo la sugerencia de Arturo, tenga en cuenta que $$\frac{1}{m!}\sum_{k=1}^{n}\dbinom{n}{k}\left(-1\right)^{k}x^{k-1}=\frac{\left(1-x\right)^{n}-1}{xm!}$$ and if we differentiate the LHS $m$ times, we get $$\frac{1}{m!}\sum_{k=1}^{n}\dbinom{n}{k}\left(-1\right)^{k}\left(k-1\right)\left(k-2\right)\cdots\left(k-m\right)x^{k-m-1}=\sum_{k=m+1}^{n}\dbinom{n}{k}\left(-1\right)^{k}\frac{\left(k-1\right)!}{m!\left(k-m-1\right)!}x^{k-m-1}$$ so we have $$\sum_{k=m+1}^{n}\dbinom{n}{k}\left(-1\right)^{k}\dbinom{k-1}{m}=\frac{1}{m!}\frac{d^{m}}{dx^{m}}\left(\frac{\left(1-x\right)^{n}-1}{x}\right)_{x=1}$$ now note that $$\frac{d}{dx}\left(\frac{\left(1-x\right)^{n}}{x}-\frac{1}{x}\right)=-\frac{n\left(1-x\right)^{n-1}}{x}-\frac{\left(1-x\right)^{n}}{x^{2}}+\frac{1}{x^{2}}$$ and $$\frac{d}{dx}\left(-\frac{n\left(1-x\right)^{n-1}}{x}-\frac{\left(1-x\right)^{n}}{x^{2}}+\frac{1}{x^{2}}\right)=\frac{2\left(1-x\right)^{n}}{x^{3}}+\frac{2n\left(1-x\right)^{n-1}}{x^{2}}+\frac{n\left(n-1\right)\left(1-x\right)^{n-2}}{x}-\frac{2}{x^{3}}$$ and so on, so you can see that, since $m<n$ we have only one term that doesn't vanish at $x=1$. Hence $$\frac{1}{m!}\frac{d^{m}}{dx^{m}}\left(\frac{\left(1-x\right)^{n}-1}{x}\right)_{x=1}=\frac{1}{m!}\left(-1\right)^{m+1}m!=\left(-1\right)^{m+1}$$ así que, finalmente,

$$\sum_{k=m+1}^{n}\dbinom{n}{k}\left(-1\right)^{k}\dbinom{k-1}{m}=\color{red}{\left(-1\right)^{m+1}}$$

como quería.

Answer 2

Para aquellos que disfrutan de las integrales de aquí es otro enfoque utilizando el Egorychev método como se presenta en muchos posts por @FelixMarin y también por @MarkusScheuer.

Supongamos que buscamos para comprobar que

$$\sum_{k=m+1}^n (-1)^k {n\choose k} {k-1\choose m} = (-1)^{m+1}.$$

Primera prueba. Introducir

$${k-1\elegir m} = {k-1\elegir k-1-m} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k-m}} (1+z)^{k-1} \; dz.$$

Ahora claramente al $k\le m$ este se desvanece así que puede reducir el límite en la suma de los $k=0.$ obtenemos

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{z^m}{1+z} \sum_{k=0}^n {n\elegir k} (-1)^k \frac{(1+z)^k}{z^k} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{z^m}{1+z} \left(1-\frac{1+z}{z} \right)^n \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{z^m}{1+z} \frac{(-1)^n}{z^n} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(-1)^n}{z^{n-m} (1+z)} \; dz = (-1)^n (-1)^{n-m-1} = (-1)^{m+1}.$$

Segunda prueba. Introducir

$${k-1\elegir m} = {k-1\elegir k-1-m} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+1}} \frac{1}{(1-z)^{k-m}} \; dz.$$

Ahora para $1\le k\le m$ esto es$[z^m] (1-z)^{m-k} = 0$, por lo que podemos de nuevo extender la suma de vuelta a $k=0$, teniendo cuidado de que el valor en $k=0$ que es $(-1)^m.$ obtenemos

$$-(-1)^m + \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+1}} (1-z)^m \sum_{k=0}^n {n\elegir k} \frac{(-1)^k}{(1-z)^k} \; dz \\ = -(-1)^m + \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+1}} (1-z)^m \left(1-\frac{1}{1-z}\right)^n \; dz \\ = -(-1)^m + \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m-n+1}} \frac{(-1)^n}{(1-z)^{n-m}} \; dz.$$

Nota sin embargo, que la $m\lt n$, por lo que la contribución de la integral se desvanece, una vez más, dejando $$(-1)^{m+1}.$$

Answer 3

Aquí está una variación basa en OPs intentos. Para ello es conveniente utilizar el coeficiente de operador $[x^k]$ para denotar el coeficiente de $x^k$ en una serie. De esta manera podemos escribir por ejemplo $$\begin{align*} (-1)^k\binom{n}{k}=[x^k](1-x)^n \end{align*}$$

Obtenemos para $0\leq m < n$

$$\begin{align*} \sum_{k=m+1}^{n}&(-1)^{k}\binom{n}{k}\binom{k-1}{m}\\ &=\sum_{k=0}^{\infty}(-1)^{k}\binom{n}{k}\binom{k-1}{k-1-m}\tag{1}\\ &=\sum_{k=0}^\infty[x^k](1-x)^n [t^{k-1-m}](1+t)^{k-1}\tag{2}\\ &=[t^{-1-m}]\frac{1}{1+t}\sum_{k=0}^\infty(1+t)^kt^{-k}[x^{k}](1-x)^n \tag{3}\\ &=[t^{-1-m}]\frac{1}{1+t}\left(1-\frac{1+t}{t}\right)^n\tag{4}\\ &=[t^{-1-m}]\frac{1}{1+t}\left(-\frac{1}{t}\right)^n\\ &=(-1)^n[t^{n-m-1}]\sum_{j=0}^\infty(-t)^j\tag{5}\\ &=(-1)^{m+1}\tag{6} \end{align*}$$ y el reclamo de la siguiente manera.

Comentario:

• En (1) utilizamos el binomio identidad $\binom{p}{q}=\binom{p}{p-q}$ y ampliar los límites de la suma sin cambiar nada, ya que estamos añadiendo ceros sólo.

• En (2) se aplica el coeficiente de operador dos veces.

• En (3) vamos a hacer algunos reordenamientos mediante el uso de la linealidad del coeficiente de operador y también utilizamos la regla $$\begin{align*} [t^{p+q}]A(t)=[t^p]t^{-q}A(t) \end{align*}$$

• En (4), usamos la regla de sustitución $$\begin{align*} A(t)=\sum_{k=0}^\infty a_kt^k=\sum_{k=0}^\infty t^k[x^k]A(x)\\ \end{align*}$$

• En (5) escribimos $t^{-n}$ como parte del coeficiente de operador (regla de (3)) y el uso de la serie geométrica de expansión de $\frac{1}{1+t}$.

• En (6) seleccionamos el coeficiente de $t^{n-m-1}$.

Answer 4

El resultado también puede ser resultado ser bastante fácilmente por inducción en $n$. En primer lugar observamos que no hay necesidad de especificar los límites de la suma: si $k>n$ o $k<m+1$, uno de los coeficientes binomiales es$0$, de todos modos. Supongamos que

$$\sum_k(-1)^k\binom{n}k\binom{k-1}m= (-1)^{m+1}$$

siempre que $0\le m<n$. A continuación, para $m<n$ hemos

$$\begin{align*} \sum_k(-1)^k\binom{n+1}k\binom{k-1}m&=\sum_k(-1)^k\left(\binom{n}k+\binom{n}{k-1}\right)\binom{k-1}m\\ &=\sum_k(-1)^k\binom{n}k\binom{k-1}m+\sum_k(-1)^k\binom{n}{k-1}\binom{k-1}m\\ &=(-1)^{m+1}+\sum_k(-1)^k\binom{n}{k-1}\binom{k-1}m\\ &=(-1)^{m+1}-\sum_k(-1)^k\binom{n}k\binom{k}m\\ &=(-1)^{m+1}-\sum_k(-1)^k\binom{n}m\binom{n-m}{n-k}\\ &=(-1)^{m+1}-\binom{n}m\sum_k(-1)^k\binom{n-m}k\\ &=(-1)^{m+1}\;, \end{align*}$$

desde $\sum_k(-1)^k\binom{r}k=0$$r\in\Bbb Z^+$.

El caso de $m=n$ es trivial, ya que la suma tiene sólo un cero término, el de $k=n+1$:

$$(-1)^{n+1}\binom{n+1}{n+1}\binom{n}n=(-1)^{n+1}\;.$$

Añadido: En realidad, lo que sugiere una combinatoria prueba de la identidad original. Supongamos que tenemos $n$ bolas blancas numeradas $1$ a través de $n$. Para un determinado $k$ hay $\binom{n}k\binom{k-1}m$ formas de elegir los $k$ de estas bolas, pintarlos de rojo, dejar de lado la bola roja con el número más grande, y, a continuación, elija $m$ restante de los $k-1$ rojo que las bolas de pintura azul. En el final tenemos los siguientes posibles resultados: un conjunto de $m$ bolas de color azul; un conjunto de $k-m$ bolas rojas, uno de los cuales tiene un número mayor que cualquiera de las bolas de color azul; y $n-k$ bolas blancas. Claramente los posibles valores de $k$ son enteros $m+1,\ldots,n$.

Alternativamente, podemos clasificar estos resultados por el conjunto de las bolas de color azul y el número de los más grandes numeradas bola roja. Para un conjunto fijo $B$ $m$ bolas de color azul y de mayor numeradas bola roja $\ell$, las cifras en el resto de las bolas de color rojo puede ser cualquier subconjunto $R$$[\ell-1]\setminus B$, y el número total de bolas rojas y azules (correspondiente a $k$ anterior) es $|R|+m+1$. Estos resultados, por tanto, contribuir

$$\begin{align*} \sum_{r=0}^{\ell-1-m}\binom{\ell-1-m}r(-1)^{r+m+1}&=(-1)^{m+1}\sum_r\binom{\ell-1-m}r(-1)^r\\ &=(-1)^{m+1}[\ell=m+1]\;, \end{align*}$$

donde $[\ell=m+1]$ es una Iverson soporte.

Es decir, sólo para $B=[m]$ $\ell=m+1$ estos resultados tienen un no-cero aporte, y en ese caso la respuesta es $(-1)^{m+1}$.