Demostración de la regla de Pascal : ${{n} \choose {r}}={{n-1} \choose {r-1}}+{{n-1} \choose r}$ cuando $1\leq r\leq n$

Question

Estoy tratando de demostrar que ${n \choose r}$ es igual a ${{n-1} \choose {r-1}}+{{n-1} \choose r}$ cuando $1\leq r\leq n$ .

Supongo que podría utilizar las reglas de conteo en probabilidad, tal vez la combinación= ${{n} \choose {r}}=\frac{n!}{r!(n-r!)}$ .

Quiero ver una prueba real detrás de esta ecuación. ¿Alguien tiene alguna idea?

Answer 1

Considere $n$ bolas en una canasta. Que haya $1$ bola roja y $n-1$ bolas azules. Ahora mira el número de formas de elegir $r$ bolas de dos maneras diferentes

Una forma es elegir $r$ bolas fuera de la $n$ bolas. Así que el número de formas es $C(n,r)$

La otra forma es mirar los casos cuando fuera de la $r$ bolas elegidas si tenemos una bola roja o no. Sólo tenemos dos opciones, a saber, fuera de la $r$ bolas podríamos tener una bola roja o ninguna bola roja

El número de formas de tener $1$ bola roja es elegir la única bola roja que se puede hacer en $C(1,1)$ formas y elegir el resto $(r-1)$ bolas de la $(n-1)$ bolas azules que se puede hacer en $C(n-1,r-1)$ maneras

Del mismo modo, el número de formas de no tener bolas rojas es elegir todas las bolas como azules, lo que se puede hacer en $C(n-1,r)$ maneras

Estos son los dos únicos casos y se excluyen mutuamente, por lo que el número total de formas es $C(n-1,r-1)+C(n-1,r)$

Por lo tanto, obtenemos $$C(n,r) = C(n-1,r-1) + C(n-1,r)$$

La misma idea podría extenderse para demostrar una generalización de lo anterior $$C(m+n,r) = \displaystyle \sum_{k=\max(0,r-n)}^{\min(r,m)} C(m,k) C(n,r-k)$$

Considere una cesta con $m$ bolas rojas y $n$ bolas azules y queremos contar el número de formas en que $r$ se pueden sacar bolas. Argumenta con dos formas diferentes de contar (igual que en el caso anterior) para demostrarlo.

Answer 2

Ya que mencionaste que te costaba visualizar esto y yo siempre me encuentro visualizándolo cada vez que tengo la necesidad de escribirlo, esto es lo que pasa por mi mente mientras el bolígrafo se mueve por el papel:

Estamos colocando $r$ bolas idénticas en $n$ cajas (como máximo una en cada una) que están en línea recta, por lo que ${ n \choose r}$ maneras de hacer esto, ahora o la última caja está vacía, eso es ${n-1 \choose r}$ maneras, o la última caja está llena, eso es ${ n-1 \choose r-1}$ formas. QED

Esto es equivalente a la respuesta de Sivaram, pero prescinde de los colores, lo que a efectos de visualización es probablemente algo más fácil.

Answer 3

Como sugirieron Sivaram y Chandru1 , un argumento combinatorio suele ser una muy buena manera de entender/probar ese tipo de identidades.

La otra forma sería, como has dicho, utilizar la fórmula explícita del coeficiente binomial:

$${{n-1} \choose {r-1}}+{{n-1} \choose r}=\frac{(n-1)!}{(n-r)!(r-1)!}+\frac{(n-1)!}{(n-r-1)!r!}$$

que se reduce a $\frac{n!}{(n-r)!r!}={n\choose r}$ .

Answer 4

Aquí tenemos una visión de esta fórmula desde una dirección diferente. Supongamos que nos dan la relación de recurrencia $R(n,k) = R(n-1,k) + R(n-1,k-1)$ , para $0 \leq k \leq n$ y la condición de contorno $R(0,k) = [k=0]$ . ¿Cómo derivarías la solución $R(n,k)$ si no sabías ya lo que era? Podrías utilizar funciones generadoras.

(Lo que sigue está tomado de Wilf's Generación de funcionalidades , 2ª edición, p. 14). Dejemos que $$G_n(x) = \sum_{k=0}^{\infty} R(n,k) x^k.$$ Multiplicando la relación de recurrencia anterior por $x^k$ y la suma de $k$ de $1$ a $\infty$ rinde $$G_n(x) -1 = G_{n-1}(x) - 1 + x G_{n-1}(x).$$ Así, $G_n(x) = (x+1)G_{n-1}(x)$ con $G_0(x) = 1$ . Así, $G_n(x) = (x+1)^n$ . Desde $R(n,k)$ es el coeficiente de $x^k$ en $(x+1)^n$ aplicando el teorema del binomio nos dice que $R(n,k) = \binom{n}{k}$ .

Answer 5

Véase esta página de Wikipedia:

• http://en.wikipedia.org/wiki/Binomial_coefficient

En la subsección Fórmula de recursión , HINT para demostrar esta fórmula. Espero que puedas hacerlo desde ahí.

La fórmula se desprende del rastreo de las contribuciones a $X^{k}$ en $(1 + X)^{n−1}(1 + X)$ o contando k-combinaciones de {1, 2, ..., n} que contienen n y que no contienen n por separado