Encuentra una demostración combinatoria para $\binom{n+1}{k} = \binom{n}{k} + \binom{n-1}{k-1} + ... + \binom{n-k}{0}$

Question

Sea $n$ y $k$ enteros con $n \geq k \geq 0$. Encuentra una prueba combinatoria para

$$\binom{n+1}{k} = \binom{n}{k} + \binom{n-1}{k-1} + \cdots + \binom{n-k}{0} .$$

Mi enfoque: Estaba pensando en usar la fórmula binomial como en $$2^n = \sum{\binom{n}{k}1^k1^{n-k}} .$$ También intenté usar la Identidad de Pascal $\binom{n}{r}=\binom{n-1}{r-1}+\binom{n-1}{r}$.

Answer 1

Creo que puedes intentar interpretar esta identidad usando el siguiente problema de la vida real:

Imagina que tienes un plato con $n+1$ golosinas: $k$ de ellas son pedazos de chocolate, y el resto son coles de Bruselas. ¿De cuántas maneras puedes comértelas todas, una por una? Supón que los pedazos de chocolate son indistinguibles entre sí, al igual que las coles de Bruselas.

La respuesta es, por supuesto, $\binom{n+1}{k}$. Sin embargo, contemos de manera diferente, dependiendo de lo que comas primero:

• Valientemente vas directamente a una col de Bruselas, antes de comer cualquier chocolate. Hay $\binom{n}{k}$ formas de hacer eso, ya que quedarán $n$ golosinas y $k$ de ellas son pedazos de chocolate;
• Primero comes un pedazo de chocolate, y luego pasas a comer una col de Bruselas: hay $\binom{n-1}{k-1}$ formas de hacer eso, ya que quedarán $n-1$ golosinas, $k-1$ de ellas de chocolate;
• Primero comes dos pedazos de chocolate, luego pasas a una col de Bruselas: de manera similar, se puede hacer en $\binom{n-2}{k-2}$ formas;
• Primero comes tres pedazos de chocolate...

etc. hasta:

• Comes primero $k-1$ pedazos de chocolate, luego una col de Bruselas. Entonces, solo una de las $n-(k-1)$ golosinas restantes es de chocolate, y la cantidad de maneras de hacerlo es $\binom{n-(k-1)}{1}$;
• Comes todos los pedazos de chocolate primero, y luego te comes todas las coles de Bruselas: se puede hacer en solo una forma, que también se puede escribir como $1=\binom{n-k}{0}$.

En general, si comes primero $m$ pedazos de chocolate ($0\le m \le k$) antes de pasar a tu primera col de Bruselas, hay $\binom{n-m}{k-m}$ formas de hacerlo: después de comer los pedazos iniciales de chocolate y la col de Bruselas, quedará n-m golosinas en el plato, k-m de ellas siendo de chocolate, por lo que puedes comértelas en $\binom{n-m}{k-m}$ formas.

En total, todos esos números deben sumar nuestro resultado original $\binom{n+1}{k}$, es decir,

$$\binom{n+1}{k}=\binom{n}{k}+\binom{n-1}{k-1}+\binom{n-2}{k-2}+\cdots+\binom{n-(k-1)}{1}+\binom{n-k}{0}=\sum_{m=0}^k\binom{n-m}{k-m}$$

Answer 2

Se sigue de la identidad de Pascal que\begin{align}\binom{n+1}k&=\binom nk+\binom n{k-1}\\&=\binom nk+\binom{n-1}{k-1}+\binom{n-1}{k-2}\\&=\binom nk+\binom{n-1}{k-1}+\binom{n-2}{k-2}+\binom{n-2}{k-3}\\&=\cdots\end{align}¿Puedes continuar a partir de aquí?

Answer 3

Una prueba combinatoria basada en caminos de rejilla.

El número de caminos de rejilla de longitud $n+1$ desde $(0,0)$ hasta $Q_k=(n-k+1,k)$ que consisten en pasos de $(1,0)$ y pasos de $(0,1)$ es $$\binom{n+1}{n-k+1}=\binom{n+1}{k}$$ ya que tenemos que elegir precisamente $n-k+1$ pasos de $(1,0)$ de un total de $n+1$ pasos.

                                

Observamos que cada camino que va desde $(0,0)$ hasta $Q_k$ cruza la línea vertical $x=n-k$. Por lo tanto, podemos particionar todos los caminos $\binom{n+1}{k}$ de acuerdo a los puntos $P_j=(n-k,j), 0\leq j\leq k$ que son seguidos por un paso horizontal hasta $(n-k+1,j)$ y los pasos verticales que llevan a $Q_k$.

Dado que hay precisamente $\binom{n-k+j}{j}$ caminos desde $(0,0)$ hasta $P_j$ el número de todos los caminos desde $(0,0)$ hasta $Q_r=(n-k+1,k)$ es \begin{align*} \color{blue}{\binom{n+1}{k}=\binom{n}{k}+\binom{n-1}{k-1}+\cdots+\binom{n-k}{0}} \end{align*}

Answer 4

Desde el triángulo de Pascal vemos que la suma es equivalente a

$$\sum_{i=n-k}^n\binom{i}{n-k}$$

luego se refiere a Identidad del palo de hockey

$$\sum^m_{i=s}{i\choose s}={m+1\choose s+1} \qquad \text{ para } m,s\in\mathbb{N}, \quad m>s$$

Answer 5

Es obvio, después de reflexionar, que ${n \choose k} ={{n-1} \choose k} +{{n-1} \choose {k-1}}$.

Solo aplica repetidamente...