Proposición
Sea $n \in \N_0$, entonces
$\dbinom{n+1}{k} = \textcolor{pink}{\dbinom{n}{k-1}} + \textcolor{lightgreen}{\dbinom{n}{k}}$, para $1 ≤ k ≤ n$
El combinatorio rosa cuenta los subconjuntos con $k$ elementos de $A_{n+1} = \{a_1, ..., a_{n+1}\}$ que contienen al elemento $a_{n+1}$ (o sea $\binom{n}{k}$).
El combinatorio verde cuenta los subconjuntos con $k$ elementos de $A_{n+1}$ que no contienen al elemento $a_{n+1}$ (o sea $\binom{n}{k}$).
Para $k = 0$ y $k= n +1$, se tiene
$$ \binom{n+1}{0} = \binom{n+1}{n+1} = 1 $$
Fórmula recursiva para calcular los números combinatorios
Notar que cada binomial es la suma de los dos que tiene en sus diagonales superiores.
Obs: Efectivamente, para $1 ≤ k ≤ n$,
$$ \dbinom{n+1}{k} = {\dbinom{n}{k-1}} + {\dbinom{n}{k}} \qquad \text{para } \binom{n}{k} = \frac {n!}{k! \cdot (n - k)!} $$
$(x + y)^n$ para $n ≥ 0$
$(x + y)^0 = 1$
$(x + y)^1 = x + y$
$(x + y)^2 = x^2 + 2xy + y^2$
Teorema
Sea $n \in \N_0$