¿Cuál es la historia que hay detrás de ${n+1 \choose k} = {n \choose k} + {n \choose k-1}$ ?

Question

Al explorar la prueba inductiva de esta pregunta

Llegué al punto de no entender este paso:

$${n+1 \choose k} = {n \choose k} + {n \choose k-1}$$

Hay una wikipedia artículo pero no tiene mucho sentido para mí.

¿Cuál es la idea detrás de este "truco"?

Answer 1

La identidad sólo divide el ${n+1 \choose k}$ en dos tipos: los subconjuntos que contienen un elemento determinado y los subconjuntos que no contienen ese elemento.

Llamemos al conjunto de $n+1$ elementos $S$ y elegir un elemento $x \in S$ .

Así que, en primer lugar, ¿cuántos subconjuntos de $S$ de tamaño $k$ contienen $x$ ? Bueno, aparte de $x$ hay $n$ elementos en $S$ . Formalmente, $|S-\{x\}| = n$ . Queremos subconjuntos de tamaño $k$ y ya tenemos $x$ en nuestro subconjunto. Por lo tanto, tenemos que elegir $k-1$ elementos de $S-\{x\}$ . Así, el número total de estos subconjuntos es ${n \choose {k-1}}$ .

En segundo lugar, ¿cuántos subconjuntos de $S$ de tamaño $k$ no contienen $x$ ? Ahora tenemos que elegir $k$ elementos de $S-\{x\}$ , lo que da ${n \choose k}$ subconjuntos.

Todos los subconjuntos de $S$ de tamaño $k$ o bien contienen $x$ o no, así que los hemos contado todos, y hemos encontrado que $${n+1 \choose k} = {n \choose k} + {n \choose k-1}.$$

Answer 2

Aunque la prueba combinatoria es definitivamente la "correcta", también se puede demostrar la identidad de Pascal utilizando la fuerza bruta, expandiendo los coeficientes del binomio: $$ \binom{n}{k} + \binom{n}{k-1} = \frac{n!}{k!(n-k)!} + \frac{n!}{(k-1)!(n-k+1)!} = \frac{n!((n-k+1)+k)}{k!(n-k+1)!} = \frac{(n+1)!}{k!(n-k+1)!} = \binom{n+1}{k}. $$

Answer 3

Uno de ellos es elegir $k$ bolas fuera de $n+1$ es lo mismo que elegir con los $n+1$ conjunto roto y el otro se debe a la propiedad del triángulo de pascal.

Answer 4

En primer lugar, $$ {n \choose k} = \frac{n!}{k!(n-k)!}$$ Siguiente, $$ {n \choose k} + {n \choose k-1} = \frac{n!}{k!(n-k)!}+\frac{n!}{(k-1)!(n-(k-1))!}$$ que es igual a $$\frac{n\cdot(n-1)...2\cdot1}{(k\cdot(k-1)...2\cdot1)((n-k)\cdot(n-k-1)...2\cdot1)}+\frac{n\cdot(n-1)...2\cdot1}{((k-1)\cdot(k-2)...2\cdot1)((n-k+1)\cdot(n-k)...2\cdot1)}$$ que es igual a $$\frac{n!}{(k-1)!(n-k)!}\Big(\frac{1}{k}+\frac{1}{n-k+1}\Big) = \frac{n!}{(k-1)!(n-k)!}\Big(\frac{(n-k+1)+k}{k(n-k)}\Big)=\frac{n!}{(k-1)!(n-k)!}\Big(\frac{n+1}{k(n-k+1)}\Big)=\frac{(n+1)\cdot n\cdot(n-1)...2\cdot1}{(k\cdot(k-1)...2\cdot1)((n-k+1)\cdot(n-k)...2\cdot1)}=\frac{(n+1)\cdot n\cdot(n-1)...2\cdot1}{(k\cdot(k-1)...2\cdot1)(((n+1)-k)\cdot(n-k)...2\cdot1)}=\frac{(n+1)!}{k!(n+1)-k)!}={(n+1) \choose k}$$

La respuesta de Yuval Filmus llegó mientras yo escribía mi respuesta. Supongo que he ampliado su solución.