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 < nDemostració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 nLa 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}