Prueba combinatoria para$\sum_{k=0}^p (-1)^k {n \choose k} = (-1)^p {n-1 \choose p}$

Question

Estoy tratando de dar una combinatoria de prueba para: $$\sum_{k=0}^p (-1)^k {n \choose k} = (-1)^p {n-1 \choose p}$$ Donde $p$ e $n$ son números naturales.

Podemos ver fácilmente que si $p=n$ esto reduce al hecho de que un juego como muchos subconjuntos de, incluso, cardinalidad, como aquellos con cardinalidad impar. Sin embargo, esta fórmula sugiere una relación entre el par y el impar cardinalidades menos que $p$.

Nota: no estoy interesado en una prueba algebraica, como Pascal identidad da una telescópica de la suma en el lado derecho.

Gracias de antemano.

Answer 1

El LHS cuenta los subconjuntos de a$\{1,2,\dots,n\}$ cuyo tamaño es en la mayoría de las $p$, incluso con subconjuntos cuenta de forma positiva y no pares de subconjuntos de contado negativamente.

Definimos un signo revertir la involución de tales subconjuntos; si $1$ es en el subconjunto de eliminar, de lo contrario, agrega. Esta involución particiones casi todos los subconjuntos de tamaño en la mayoría de las $p$ en pares que se cancelan entre sí en la suma.

La única impares subconjuntos son aquellos con un tamaño exactamente $p$ que no contengan $1$, como la adición de $1$ haría un subconjunto de tamaño $p+1$. El número de subconjuntos de a$\binom{n-1}p$, y se cuentan con signo $(-1)^p$.