Prueba de identidad combinatoria que involucra (-1)^k[(n - 1) Cr k]

Question

Dada la siguiente identidad: $$ \sum_ {i=0}^k (-1)^i \binom ni = (-1)^k \binom {n-1}{k}$$

Esto se puede probar por inducción, sin embargo me pregunto si hay una manera de probar esto de manera combinatoria (algo como subconjuntos, grupos, elegir n bolas de una caja con k bolas, etc.)

Gracias.

Answer 1

El lado izquierdo de tu ecuación es un recuento ponderado de los subconjuntos de $\{1, \dots ,n\}$ de todos los tamaños $i$ de 0 a $k$ los pesos son $1$ o $-1$ de acuerdo con $i$ es par o impar. Podemos emparejar la mayoría de estos subconjuntos de la siguiente manera: Si un conjunto $X$ contiene $n$ y lo empareje con $X-\{n\}$ si no contiene $n$ y lo empareje con $X \cup\ {n\}$ . Tenga en cuenta que esto es realmente un emparejamiento; si nos emparejamos $X$ con $Y$ entonces también nos emparejamos $Y$ con $X$ . Dos conjuntos emparejados contribuyen con signos opuestos a su suma, por lo que sus contribuciones se cancelan, y la suma se reduce a los conjuntos no emparejados. Pero estos son solo los conjuntos que tienen $k$ elementos y no contienen $n$ . Cualquier conjunto más pequeño puede ser emparejado, como se ha descrito, por la adición o la eliminación de $n$ y un conjunto de tamaño $k$ que contiene $n$ puede ser emparejado como se describe, quitando $n$ . Sólo cuando un conjunto no contiene $n$ (así que queremos adjuntar $n$ ) y tiene un tamaño $k$ (de modo que al adjuntar un elemento haría su tamaño inadmisiblemente grande) hay un fallo en el emparejamiento. Los conjuntos no apareados, los conjuntos de tamaño $k$ que no contienen $n$ todos contribuyen con el signo $(-1)^k$ y hay $ \binom {n-1}k$ de ellos. De ahí el lado derecho de tu ecuación.