La búsqueda de una combinatoria prueba de $\sum\limits _{k=3}^n k \binom{k}{3}=3 \binom{n+1}{4}+4 \binom{n+1}{5}$

Question

Agradecería si alguien me podría ayudar con el siguiente problema

P: en Busca de una combinatoria de prueba

$$ \la suma de _{k=3}^n k \binom{k}{3} =3 \binom{n+1}{4}+4 \binom{n+1}{5} $$

Answer 1

Recordemos que $|x|_a$ es el número de veces que la cadena de $x$ contiene una letra de la a, en otras palabras $|x|_a=|\{i:x_i=a\}|.$

Imaginar una cadena de $x\in \{0,\color{red}{1},\color{green}{2},\color{blue}{3}\}^{n+1},$ consideran que el set $$A=\{x\in \{0,\color{red}{1},\color{green}{2},\color{blue}{3}\}^{n+1}:|x|_2=|x|_3=1,|x|_1\in \{2,3\}\text{ and if $x_j=\color{blue}{3}$ then $x_k=0$ for k>j}\}$$ and consider the sets $A_k=\{x\in A: \text{para $j> k$ $x_j=0$ y $x_k=\color{blue}{3}$} \}.$

Entonces $$|A|=\sum _{k=4}^{n+1}|A_k|,$$ but $|A_k|=\binom{k-1}{3}(k-1)$ where the binomial is for choosing the $\color{red}{1}s$ and $(k-1)$ is for choose the $\color{green}{2}.$ (if you choose a spot that has a $\color{red}{1}$ for the $\color{green}{2}$ is still fine because now you have $2$ $\color{red}{1s}$.)

But also $|A|=\binom{n+1}{4}3+\binom{n+1}{5}4$ because either you choose $3$ spots for a $\color{green}{2}$ and two $\color{red}{1s}$ or $4$ spots for one $\color{green}{2}$ and three $\color{red}{1s}.$
Por la doble contabilización de obtener la identidad.

Edit: he puesto los colores en las letras que pertenecen a las cadenas para no confundirlo con el número total de esos símbolos.

Answer 2

En primer lugar vamos a demostrar que $$\sum_{m=k}^n \binom{m}{k} = \binom{n+1}{k+1}$$ combinatoria.

Contamos el número de $(k+1)$ subconjuntos de a $\{1,2,\ldots, n+1\}$. Por definición, esto es $\binom{n+1}{k+1}$.

Considerar el mayor número en el subconjunto. Esto puede ser $m+1$ e las $k+1$ subconjunto puede ser elegido con $m+1$ como el elemento más grande en $\binom{m}{k}$ maneras. Por lo tanto tenemos la anterior igualdad.

Ahora, la suma puede ser escrito como $$\sum _{k=3}^n k \binom{k}{3} = \sum_{k=3}^n \left\{4\binom{k}{4} + 3\binom{k}{3}\right\}$$ De lo anterior, el resultado de la siguiente manera.