Double Counting(combinatorial proof) for $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

can anyone help me with double-counting proof for this equation: $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}$

I tried this example: we have n+1 bits and at least two "1" bits. it gives just the right side. and also looking at right side in $\binom{n+1}{2}2^{n-1}$ may help.

Answer 1

Both sides count the combinations of subsets of $[n]$ with ordered pairs of elements of that subset. On the left, we first choose one of $\binom nk$ subsets with $k$ elements and then choose one of the $k^2$ ordered pairs of its elements. On the right, we first choose an ordered pair of elements and then a subset containing the elements: For the $n(n-1)$ pairs of different elements there are $2^{n-2}$ subsets containing them, and for the $n$ pairs of identical elements there are $2^{n-1}$ subsets containing them, for a total of $n(n-1)2^{n-2}+n2^{n-1}=n(n+1)2^{n-2}$.

Answer 2

I only know how to prove it analytically. Let $f(x)=(1+x)^{n}=\sum_{k=0}^{n}{n \choose k}x^{k}.$ Differentiating, we have $$ f'(x)=\sum_{k=1}^{n}kx^{k-1}{n \choose k}. $$ Multiply both sides by $x$ and differentiate them again, then we have \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*} Put $x=1$, then we have \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*} provided that $n\geq2$.