Regla de Pascal : Definición y demostración

En combinatoria, la regla de pascal dice que para cada número natural $n$ se tiene lo siguiente:

\binom{n-1}{k-1} +\binom{n-1}{k} = \binom{n}{k}, \quad 1 \leq k < n

Demostración

Partamos de un lado de la igualdad y desarrollemos para obtener el otro:

\binom{n-1}{k-1} +\binom{n-1}{k}

Aplicamos la definición de coeficiente binomial:

\binom{n-1}{k-1} +\binom{n-1}{k} = \frac{(n-1)!}{([n-1]-[k-1])!(k-1)!} + \frac{(n-1)!}{([n-1]-k)!(k)!}

Simplificamos el denominador de la primera expresión y ordenamos un poco:

\frac{(n-1)!}{([n-1]-[k-1])!(k-1)!} + \frac{(n-1)!}{([n-1]-k)!(k)!} = \frac{(n-1)!}{(n-1-k+1)!(k-1)!} + \frac{(n-1)!}{(n-k-1)!(k)!} = \frac{(n-1)!}{(n-k)!(k-1)!} + \frac{(n-1)!}{(n-k-1)!(k)!}

Obtenemos en mínimo común múltiplo de los denominadores: $(n-k)!(k)!$ Y sumamos esas dos fracciones:

\frac{(n-1)!}{(n-k)!(k-1)!} + \frac{(n-1)!}{(n-k-1)!(k)!} = \frac{(n-1)!(k)+(n-1)!(n-k)}{(n-k)!(k)!}

Usamos la propiedad distributiva en el numerador para $(n-1)!$ y simplificamos:

\frac{(n-1)!(k)+(n-1)!(n-k)}{(n-k)!(k)!} = \frac{(n-1)!(k+[n-k])}{(n-k)!(k)!} = \frac{(n-1)!(k+n-k)}{(n-k)!(k)!}= \frac{(n-1)!(n)}{(n-k)!(k)!}

Veamos esta definición de factorial:

n! = (n-1)!\cdot n

La usaremos en el numerador:

\frac{(n-1)!(n)}{(n-k)!(k)!} = \frac{n!}{(n-k)!(k)!}

Aplicando la definición de factorial:

\frac{n!}{(n-k)!(k)!} = \binom{n}{k}

Por transitividad:

\binom{n-1}{k-1} +\binom{n-1}{k} = \binom{n}{k}