Prueba con argumento combinatorio

Question

Demuestre con un argumento combinatorio que esto es igual :

$$\dbinom{n}{k+1} = \dbinom{n-1}{k}+ \dbinom{n-2}{k} +...+ \dbinom{k}{k}$$

No tengo ni idea de cómo hacerlo, así que sería de gran ayuda si alguien conoce alguna forma.

Answer 1

Supongamos que queremos distribuir $n - k - 1$ bolas idénticas en $k + 2$ cajas distintas. Con las estrellas y las barras, hay $\binom{n - k - 1 + k + 1}{k + 1} = \binom{n}{k + 1}$ formas de hacerlo.

También podemos distribuir primero $0 \le i \le n - k - 1$ bolas en la primera caja y luego distribuir el resto de las bolas en las restantes $k + 1$ cajas. El número de formas de hacerlo es, usando estrellas y barras para las bolas y cajas restantes, es

$$\binom{(n - k - 1) + k}{k} + \binom{(n - k - 2) + k}{k} + \dots + \binom{(n - k - n) + k}{k}$$ $$= \binom{n - 1}{k} + \binom{n - 2}{k} + \dots + \binom{k}{k}$$

Como ambas formas de contar son equivalentes, tenemos

$$\binom{n}{k + 1} = \binom{n - 1}{k} + \binom{n - 2}{k} + \dots + \binom{k}{k}$$