Recurrencia de Pascal

Teoría

La Recurrencia de Pascal, también conocida como la Identidad de Pascal, es la relación fundamental que define la estructura del Triángulo de Pascal. Dice que cualquier coeficiente binomial es la suma de los dos coeficientes que están justo arriba de él en el triángulo. Algebraicamente, esto te permite calcular el número de formas de elegir $k$ elementos de un conjunto de $n$ elementos al reducir el problema a subconjuntos más pequeños. Esta definición recursiva es el método principal para generar coeficientes binomiales sin que tengas que calcular factoriales grandotes directamente.

En el contexto de competencias de combinatoria como el AMC 10/12, esta identidad es esencial para simplificar problemas de conteo complejos y demostrar identidades más avanzadas usando inducción. Muchas veces puedes explicar la intuición detrás de la recurrencia usando el argumento del "elemento distinguido". Si quieres formar un comité de $k$ personas de un grupo de $n$ personas, puedes enfocarte en una persona específica, digamos Alice. Hay dos casos que no pueden pasar al mismo tiempo: o Alice está en el comité, o no está. Si incluyes a Alice, tienes que elegir a los $k-1$ miembros restantes de las $n-1$ personas que quedan. Si la excluyes, tienes que elegir a los $k$ miembros de las $n-1$ personas que quedan. La suma de estos dos casos cubre todas las posibilidades.

Fórmulas Clave

La relación de recurrencia fundamental para enteros no negativos $n$ y $k$ donde $1 \leq k \leq n$ es:

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

Para que puedas definir por completo los valores de los coeficientes binomiales de forma recursiva, también necesitas las condiciones de frontera (las orillas del Triángulo de Pascal):

$$ \binom{n}{0} = 1 \quad \text{y} \quad \binom{n}{n} = 1 $$

Si usas la definición de factorial de los coeficientes binomiales, puedes ver cómo la identidad se relaciona con:

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

Demostración

Para demostrar la Identidad de Pascal, usa la manipulación algebraica de la definición de los coeficientes binomiales con factoriales.

Teorema: Para enteros $n, k$ tales que $1 \leq k \leq n$, $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$.

Demostración: Recuerda la definición del coeficiente binomial: $\binom{n}{k} = \frac{n!}{k!(n-k)!}$.

Empieza con el lado derecho de la identidad y manipúlalo hasta que sea igual al lado izquierdo.

$$ \text{Lado Derecho} = \binom{n-1}{k-1} + \binom{n-1}{k} $$

Sustituye las definiciones con factoriales:

$$ \text{Lado Derecho} = \frac{(n-1)!}{(k-1)!((n-1)-(k-1))!} + \frac{(n-1)!}{k!((n-1)-k)!} $$

Simplifica los factoriales en los denominadores:

$$ \text{Lado Derecho} = \frac{(n-1)!}{(k-1)!(n-k)!} + \frac{(n-1)!}{k!(n-k-1)!} $$

Para sumar estas fracciones, busca un denominador común. El mínimo común múltiplo de los denominadores es $k!(n-k)!$.

• Para el primer término, multiplica el numerador y el denominador por $k$ (ya que $k! = k \cdot (k-1)!$).
• Para el segundo término, multiplica el numerador y el denominador por $(n-k)$ (ya que $(n-k)! = (n-k) \cdot (n-k-1)!$).

$$ \text{Lado Derecho} = \frac{k \cdot (n-1)!}{k!(n-k)!} + \frac{(n-k) \cdot (n-1)!}{k!(n-k)!} $$

Ahora, combina los numeradores sobre el denominador común:

$$ \text{Lado Derecho} = \frac{(n-1)! \cdot [k + (n-k)]}{k!(n-k)!} $$

Simplifica la expresión dentro de los corchetes:

$$ \text{Lado Derecho} = \frac{(n-1)! \cdot n}{k!(n-k)!} $$

Cuando te das cuenta de que $n \cdot (n-1)! = n!$, obtienes:

$$ \text{Lado Derecho} = \frac{n!}{k!(n-k)!} $$

Esto es exactamente la definición de $\binom{n}{k}$. Por lo tanto:

$$ \text{Lado Derecho} = \binom{n}{k} = \text{Lado Izquierdo} $$

$\square$