Identidad del palo de hockey

En matemática combinatoria se conoce como Identidad del palo de hockey^[1] o Identidad del Calcetín de Navidad^[2] a la igualdad:

$\sum_{i = r}^{n} (\binom{i}{r}) = (\binom{n + 1}{r + 1}) \forall n, r \in ℕ & n \geq r$

o a su imagen equivalente mediante la sustitución $j \to i - r$ :

$\sum_{j = 0}^{n - r} (\binom{j + r}{r}) = (\binom{n + 1}{n - r})$

la cual representa la suma de $n$ o $n - r + 1$ elementos, en la segunda igualdad, de una diagonal del triángulo de Pascal. El nombre de esta igualdad proviene de su representación gráfica sobre dicho triángulo, ya que cuando se resaltan los sumandos y el total, la forma revelada recuerda vagamente a esos objetos.

Demostraciones

Como paso previo a las demostraciones, hay que recordar la llamada Regla de Pascal que relaciona los elementos de una fila del triángulo de Pascal con los de la fila siguiente:

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

O a su equivalente:

$(\binom{n + 1}{k + 1}) = (\binom{n}{k}) + (\binom{n}{k + 1})$

Inducción matemática

Sea $n = r$

$\sum_{i = r}^{n} (\binom{i}{r}) = \sum_{i = r}^{r} (\binom{i}{r}) = 1 = (\binom{r + 1}{r + 1}) = (\binom{n + 1}{r + 1})$

Supongamos que la identidad se cumple para todo número $k \in ℕ, k \geq r$ , por lo que es válido expresar que:

$\sum_{i = r}^{k} (\binom{i}{r}) = (\binom{k + 1}{r + 1})$

Entonces, la igualdad debe cumplirse para el número $k + 1$ :

$\begin{matrix} \sum_{i = r}^{k + 1} (\binom{i}{r}) & = \sum_{i = r}^{k} (\binom{i}{r}) + (\binom{k + 1}{r}) \\ = (\binom{k + 1}{r + 1}) + (\binom{k + 1}{r}) \\ = (\binom{k + 2}{r + 1}) \end{matrix}$

Por lo que queda demostrada la identidad de manera inductiva.

Prueba algebraica (I)

Tomemos la identidad básica y usemos la ecuación equivalente de la Identidad de Pascal de manera directa:

\begin{matrix} \sum_{t = k}^{n} (\binom{t}{k}) & = \sum_{t = k}^{n} [(\binom{t + 1}{k + 1}) - (\binom{t}{k + 1})] \\ = \sum_{t = k}^{n} (\binom{t + 1}{k + 1}) - \sum_{t = k}^{n} (\binom{t}{k + 1}) \\ = \sum_{t = k + 1}^{n + 1} (\binom{t}{k + 1}) - \sum_{t = k}^{n} (\binom{t}{k + 1}) & Cambio de variables \\ = (\binom{n + 1}{k + 1}) - \underset{0}{\underset{⏟}{(\binom{k}{k + 1})}} & Desarrollo de los sumatorios \\ = (\binom{n + 1}{k + 1}) & Resultado final \end{matrix}

Prueba algebraica (II)

Consideremos la serie geométrica: $S = 1 + (1 + x) + (1 + x)^{2} + (1 + x)^{3} + \dots + (1 + x)^{n}$

Ya que la razón de esta serie es $(1 + x)$ , la igualdad anterior se transforma en:

$\begin{matrix} 1 + (1 + x) + (1 + x)^{2} + (1 + x)^{3} + \dots + (1 + x)^{n} & = \frac{(1 + x)^{n + 1} - 1}{(1 + x) - 1} \\ = \sum_{j = 1}^{n + 1} (\binom{n + 1}{j}) x^{j - 1} \end{matrix}$

Desarrollemos los diferentes binomios a partir de $(1 + x)^{k}$ :

$\begin{matrix} (1 + x)^{k} & = (\binom{k}{0}) + \dots + (\binom{k}{k}) x^{k} \\ (1 + x)^{k + 1} & = (\binom{k + 1}{0}) + \dots + (\binom{k + 1}{k}) x^{k} + (\binom{k + 1}{k + 1}) x^{k + 1} \\ (1 + x)^{k + 2} & = (\binom{k + 2}{0}) + \dots + (\binom{k + 2}{k}) x^{k} + (\binom{k + 2}{k + 1}) x^{k + 1} + (\binom{k + 2}{k + 2}) x^{k + 2} \\ \dots \\ (1 + x)^{n} & = (\binom{n}{0}) + \dots + (\binom{n}{k}) x^{k} + \dots + (\binom{n}{n}) x^{n} \end{matrix}$

Al sumar todos los coeficientes binomiales del término $x^{k}$ y sustituir después $j \to k + 1$ obtenemos:

$\begin{matrix} [r l r] (\binom{k}{k}) + (\binom{k + 1}{k}) + (\binom{k + 2}{k}) + \dots + (\binom{n}{k}) & = & (\binom{n + 1}{k + 1}) \\ \sum_{j = 0}^{n - k} (\binom{k + j}{k}) & = & (\binom{n + 1}{k + 1}) \\ \sum_{t = k}^{n} (\binom{t}{k}) & = & (\binom{n + 1}{k + 1}) & Haciendo cambio de variable \end{matrix}$

con lo que queda demostrada la identidad.

Prueba combinatoria (I)

Imagine que estamos distribuyendo caramelos indistinguibles a niños distinguibles. Mediante una aplicación directa del método de estrellas y barras, existen

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

formas de distribuirlos. De manera alterna, primero podemos darle $0 \leq i \leq n$ caramelos al mayor de los niños, de modo que en esencia, damos $n - i$ caramelos a los $k - 1$ niños restantes.y, nuevamente, mediante doble conteo y el método de las estrellas y barras, nosotros tenemos:

$(\binom{n + k - 1}{k - 1}) = \sum_{i = 0}^{n} (\binom{n + k - 2 - i}{k - 2})$

lo cual se simplifica al resultado deseado, haciendo un cambio de variable, al tomar $n^{'} = n + k - 2$ y $r = k - 2$ y observando que $n^{'} - n = k - 2 = r$ :

$(\binom{n^{'} + 1}{r + 1}) = \sum_{i = 0}^{n} (\binom{n^{'} - i}{r}) = \sum_{i = r}^{n^{'}} (\binom{i}{r})$

Prueba combinatoria (II)

Podemos formar un comité de un tamaño de $k + 1$ personas a partir de un grupo de $n + 1$ personas en

(\binom{n + 1}{k + 1})

maneras. Ahora entregamos números como $1, 2, 3, \dots, n - k + 1$ a $n - k + 1$ de las $n + 1$ personas. Podemos dividir esto en $n - k + 1$ casos inconexos. En general, en el caso de un número $x$ , tal que $1 ⩽ x ⩽ n - k + 1$ , la persona con el número $x$ está en el comité y las personas $1, 2, 3, \dots, x - 1$ no están en dicho comité. Esto se puede hacer de

(\binom{n - x + 1}{k})

maneras. Ahora, podemos sumar los valores de estos $n - k + 1$ casos diferentes, obteniendo:

(\binom{n + 1}{k + 1}) = (\binom{n}{k}) + (\binom{n - 1}{k}) + (\binom{n - 2}{k}) + \dots + (\binom{k + 1}{k}) + (\binom{k}{k}) .

lo que, nuevamente prueba la identidad.

Véase también

Enlaces externos

Referencias

Plantilla:Listaref Plantilla:Control de autoridades

[1] Plantilla:Cita publicación

[2] Plantilla:Cita web

[1]

[2]

Identidad del palo de hockey

Sumario

Demostraciones

Inducción matemática

Prueba algebraica (I)

Prueba algebraica (II)

Prueba combinatoria (I)

Prueba combinatoria (II)

Véase también

Enlaces externos

Referencias

Menú de navegación

Identidad del palo de hockey

Demostraciones

Inducción matemática

Prueba algebraica (I)

Prueba algebraica (II)

Prueba combinatoria (I)

Prueba combinatoria (II)

Véase también

Enlaces externos

Referencias

Menú de navegación

Buscar