Prueba combinatoria de la identidad ${n+1\choose k+1}={k\choose k}+{k+1\choose k}+...+{n-1\choose k}+{n\choose k}$

Question

WTS: ${n+1\choose k+1}={k\choose k}+{k+1\choose k}+...+{n-1\choose k}+{n\choose k}.$

Algebraico, es posible, aunque tedioso Mostrar. ¿Hay cualquier aproximación combinatoria para demostrar este hecho?

Answer 1

Estamos eligiendo $k+1$ números de los números de $1,2,3,\dots,n+1$. Hay $\binom{n+1}{k+1}$ maneras de hacer esto. Que nos permiten contar el número de opciones de otra manera.

Quizás $1$ es el menor número elegido. Luego hay $\binom{n}{k}$ formas de elegir el resto de $k$.

Quizás $2$ es el menor número elegido. Luego hay $\binom{n-1}{k}$ formas de elegir el resto de $k$.

Quizás $3$ es el menor número elegido. Luego hay $\binom{n-2}{k}$ formas de elegir el resto de $k$.

Y así sucesivamente. Agregar para arriba. Obtenemos nuestros suma (hacia atrás).