Prueba de la identidad del palo de hockey

Question

Después de leer esta pregunta la respuesta más popular utiliza la identidad $$\sum_{t=0}^n \binom{t}{k} = \binom{n+1}{k+1} .$$

¿Cuál es el nombre de esta identidad? ¿Es la identidad del El triángulo de Pascal modificado.

¿Cómo podemos probarlo? Lo he intentado por inducción, pero sin éxito. ¿Podemos demostrarlo también algebraicamente?

Gracias por su ayuda.

---

EDIT 01 : Esta identidad se conoce como identidad del palo de hockey porque, en el triángulo de Pascal, cuando se resaltan los sumandos representados en la suma y la propia suma, un palo de hockey se revela la forma.

Answer 1

Imagina la primera $n + 1$ números, escritos en orden en un papel. En la parte derecha se pregunta de cuántas maneras se puede elegir $k+1$ de ellos. ¿De cuántas maneras se puede hacer esto?

Primero se elige un número más alto, que se rodea con un círculo. Llámalo $s$ . A continuación, todavía tiene que elegir $k$ números, cada uno menor que $s$ y hay $\binom{s - 1}{k}$ formas de hacerlo.

Desde $s$ oscila entre $1$ a $n$ , $t:= s-1$ oscila entre $0$ a $n$ como se desee.

Answer 2

$$\begin{align} \sum_{t=\color{blue}0}^n \binom{t}{k} =\sum_{t=\color{blue}k}^n\binom tk&= \sum_{t=k}^n\left[ \binom {t+1}{k+1}-\binom {t}{k+1}\right]\\ &=\sum_{t=\color{orange}k}^\color{orange}n\binom {\color{orange}{t+1}}{k+1}-\sum_{t=k}^n\binom t{k+1}\\ &=\sum_{t=\color{orange}{k+1}}^{\color{orange}{n+1}}\binom {\color{orange}{t}}{k+1}-\sum_{t=k}^n\binom t{k+1}\\ &=\binom{n+1}{k+1}-\underbrace{\binom k{k+1}}_0\\ &=\binom{n+1}{k+1}\quad\blacksquare\\ \end{align}$$

Answer 3

Esto es puramente algebraico. En primer lugar, dado que $\dbinom{t}{k} =0$ cuando $k>t$ podemos reescribir $$\binom{n+1}{k+1} = \sum_{t=0}^{n} \binom{t}{k}=\sum_{t=k}^{n} \binom{t}{k}$$

Recordemos que (por el triángulo de Pascal), $$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$

Por lo tanto, $$\binom{t+1}{k+1} = \binom{t}{k} + \binom{t}{k+1} \implies \binom{t}{k} = \binom{t+1}{k+1} - \binom{t}{k+1}$$

Resumamos esto con $t$ : $$\sum_{t=k}^{n} \binom{t}{k} = \sum_{t=k}^{n} \binom{t+1}{k+1} - \sum_{t=k}^{n} \binom{t}{k+1}$$

Factoricemos el último miembro de la primera suma y el primer miembro de la segunda suma: $$\sum _{t=k}^{n} \binom{t}{k} =\left( \sum_{t=k}^{n-1} \binom{t+1}{k+1} + \binom{n+1}{k+1} \right) -\left( \sum_{t=k+1}^{n} \binom{t}{k+1} + \binom{k}{k+1} \right)$$

Obviamente $\dbinom{k}{k+1} = 0$ por lo que obtenemos $$\sum _{t=k}^{n} \binom{t}{k} =\binom{n+1}{k+1} +\sum_{t=k}^{n-1} \binom{t+1}{k+1} -\sum_{t=k+1}^{n} \binom{t}{k+1}$$

Presentemos $t'=t-1$ , entonces si $t=k+1 \dots n, t'=k \dots n-1$ Por lo tanto $$\sum_{t=k}^{n} \binom{t}{k} = \binom{n+1}{k+1} +\sum_{t=k}^{n-1} \binom{t+1}{k+1} -\sum_{t'=k}^{n-1} \binom{t'+1}{k+1}$$

Los dos últimos argumentos se eliminan entre sí y se obtiene la formulación deseada $$\binom{n+1}{k+1} = \sum_{t=k}^{n} \binom{t}{k} = \sum_{t=0}^{n} \binom{t}{k}$$

Answer 4

Puede utilizar la inducción en $n$ observando que

$$\sum_{t=0}^{n+1} \binom{t}{k} = \sum_{t=0}^{n} \binom{t}{k} + \binom{n+1}{k} = \binom{n+1}{k+1} + \binom{n+1}{k} = \binom{n+2}{k+1}$$

Answer 5

Otra técnica consiste en utilizar aceite de serpiente . Llama a tu suma:

$\begin{align} S_k &= \sum_{0 \le t \le n} \binom{t}{k} \end{align}$

Definir la función generadora:

$\begin{align} S(z) &= \sum_{k \ge 0} S_k z^k \\ &= \sum_{k \ge 0} z^k \sum_{0 \le t \le n} \binom{t}{k} \\ &= \sum_{0 \le t \le n} \sum_{k \ge 0} \binom{t}{k} z^k \\ &= \sum_{0 \le t \le n} (1 + z)^t \\ &= \frac{(1 + z)^{n + 1} - 1}{(1 + z) - 1} \\ &= z^{-1} \left( (1 + z)^{n + 1} - 1 \right) \end{align}$

Por tanto, nos interesa el coeficiente de $z^k$ de esto:

$\begin{align} [z^k] z^{-1} \left( (1 + z)^{n + 1} - 1 \right) &= [z^{k + 1}] \left( (1 + z)^{n + 1} - 1 \right) \\ &= \binom{n + 1}{k + 1} \end{align}$