Recuento doble (prueba combinatoria) para $1^2\binom{n}{1} + 2^2\binom{n}{2}+3^2\binom{n}{3}+...+n^2\binom{n}{n}$ = $n(n+1)2^{n-2}$

Question

¿alguien puede ayudarme con la prueba de doble contabilidad para esta ecuación? $1^2\binom{n}{1} + 2^2\binom{n}{2}+3^2\binom{n}{3}+...+n^2\binom{n}{n}$ = $n(n+1)2^{n-2}$

He probado este ejemplo: tenemos n+1 bits y al menos dos bits "1". da sólo el lado derecho. y también mirando el lado derecho en $\binom{n+1}{2}2^{n-1}$ puede ayudar.

Answer 1

Ambas partes cuentan las combinaciones de subconjuntos de $[n]$ con pares ordenados de elementos de ese subconjunto. A la izquierda, elegimos primero uno de $\binom nk$ subconjuntos con $k$ y luego elegir uno de los elementos $k^2$ pares ordenados de sus elementos. A la derecha, elegimos primero un par ordenado de elementos y luego un subconjunto que contenga los elementos: Para el $n(n-1)$ pares de elementos diferentes hay $2^{n-2}$ subconjuntos que los contienen, y para el $n$ pares de elementos idénticos hay $2^{n-1}$ subconjuntos que los contienen, para un total de $n(n-1)2^{n-2}+n2^{n-1}=n(n+1)2^{n-2}$ .

Answer 2

Sólo sé demostrarlo analíticamente. Sea $f(x)=(1+x)^{n}=\sum_{k=0}^{n}{n \choose k}x^{k}.$ Diferenciando, tenemos $$ f'(x)=\sum_{k=1}^{n}kx^{k-1}{n \choose k}. $$ Multiplica ambos lados por $x$ y los diferenciamos de nuevo, entonces tenemos \begin{eqnarray*} \frac{d}{dx}\{xf'(x)\} & = & \frac{d}{dx}\sum_{k=1}^{n}kx^{k}{n \choose k}\\ f'(x)+xf''(x) & = & \sum_{k=1}^{n}k^{2}x^{k-1}{n \choose k}. \end{eqnarray*} Poner $x=1$ entonces tenemos \begin{eqnarray*} & & \sum_{k=1}^{n}k^{2}{n \choose k}\\ & = & f'(1)+f''(1)\\ & = & n\cdot2^{n-1}+n(n-1)2^{n-2}\\ & = & 2^{n-2}n(n+1), \end{eqnarray*} siempre que $n\geq2$ .