Supongo que esto es simple. Sin embargo, mis matemáticas son oxidados y mi frustración creciente. ¿Cómo se puede demostrar que
$$\sum _{k=0}^p \binom{n}{k} (n-2 k) = (p+1) \binom{n}{p+1}$$
se mantiene?
Respuestas
¿Demasiados anuncios?
$$\binom nk (n-2k)=\frac{n!}{(n-k)! k!} (n-k-k)$$
$$=n\left(\frac{(n-1)!}{(n-1-k)!k!}-\frac{(n-1)!}{\{(n-1)-(k-1)\}!(k-1)!}\right) $$
$$=n\left(\binom{n-1}k -\binom{n-1}{k-1}\right) $$
La observación de la antena Telescópica de Suma/de la Serie,
$$\sum _{k=0}^p \binom{n}{k} (n-2 k) = n\cdot \binom{n-1}p$$
$$=n\cdot\frac{(n-1)!}{(n-1-p)!p!}=(p+1)\cdot \frac{n!}{\{n-(p+1)\}!(p+1)!}=(p+1)\cdot\binom n{p+1}$$
GmonC
Puntos
114
La respuesta por laboratorio bhattacharjee me pregunto si hay una forma simple de bijective explicación de este curioso identidad (curiosa para mí, porque yo nunca había visto antes, y porque creo que el $(a+bk)\binom nk$ $a,b,n$ constante es sólo summable en$~k$ en forma cerrada para $(a,b)=(n,-2)$). En efecto, a pesar de la prohibición buscando factoriales, la única identidades que realmente se necesita son la "absorción" identidad " $k\binom nk=n\binom{n-1}{k-1}$ y su variante $(n-k)\binom nk=n\binom{n-1}k$). Aquí es cómo:$$ \begin{aligned} \sum_{k=0}^p (n-2k)\binom nk &= \sum_{k=0}^p \left((n-k)\binom nk -k\binom nk\right) \\&= \sum_{k=0}^p \left(n\binom{n-1}k-n\binom{n-1}{k-1}\right) \\&=n\left(\binom{n-1}p-\binom{n-1}{-1}\right) \\&=n\binom{n-1}p \\&= (p+1)\binom n{p+1}. \end{aligned} $$ Ahora por un lado la absorción de las leyes de tener un simple bijective prueba, y por otro lado, siendo el polinomio de identidades en$~n$ (de grados $k,k+1$, respectivamente) son válidas sin la suposición de que $n$ es un entero positivo. Así la identidad demostrado sostiene arbitrarias $n$ (negativos, fraccionarios, complejo, indeterminado) y para cualquier entero no negativo,$~p$ (sin necesidad de que asuman $p\leq n$).
Ahora para un bijective prueba, en un conjunto de $n$ frutas diferentes, de los cuales seleccionamos uno, y de que un subconjunto de a la mayoría de las $p$ resulta ser malo malo; contamos el número de configuraciones posibles, pero con un signo menos en el caso de que el seleccionado fruto es malo. La fijación de un subconjunto de a $k\leq p$ malos frutos, hay $n-k$ buena y $k$ malas selecciones posibles, por lo que este subconjunto contribuye $(n-k)-k=n-2k$ a la suma final; esta suma es el dado por el lado izquierdo. Contar de manera diferente, podemos cancelar la mayoría de las configuraciones contra uno con el signo opuesto por el cambio de la buena/mala condición de la fruta seleccionada (esto claramente pares de configuraciones); sin embargo cuando hay exactamente $p$ malos frutos y bueno uno de ellos es seleccionado, este cambio no se puede hacer debido a la "en la mayoría de las $p$ mala friuts" restricción. Por lo que el total de la configuración de la suma es el (no negativo) de la serie de los impares configuraciones, con $p$ malos frutos y una buena fruta seleccionada. Estos pueden ser contados como $n\binom{n-1}p$ (seleccione una fruta y hacer $p$ restante de los frutos malos), o como $(p+1)\binom n{p+1}$ (elegir el $p+1$-subconjunto de mal-o bien-selecciona las frutas en primer lugar, a continuación, elija la fruta seleccionada entre ellos, por lo que es bueno y otros malos).
