Give a combinatorial proof: $ n(n+1)2^{n-2} = \sum_{k=1}^{n}k^2\binom{n}{k} $

Solution 1:

Assume that you have a group of $n$ people and two medals, a gold medal and a silver medal.
Assume that you want to count in how many ways you may select $k\geq 1$ people and give the two medals to someone in this group (with the chance to give the two medals to the same person).
If you choose the group first, you have $$ \sum_{k\geq 1}\binom{n}{k}k^2 $$ ways for doing that. Otherwise, you may first give the gold medal to someone in the initial group ($n$ ways for doing that), then give the silver medal, then choose who else belong to the group of "elected" people. If the silver medal does not go to the gold medalist, you have $n(n-1)2^{n-2}$ ways. If the silver medal goes to the gold medalist, you have $n 2^{n-1}$ ways, and $$ n(n-1)2^{n-2}+n 2^{n-1} = n(n+1)2^{n-2} $$ as wanted.

Now an alternative. Since $k\binom{n}{k}=n\binom{n-1}{k-1}$ and $(k-1)\binom{n-1}{k-1}=(n-1)\binom{n-2}{k-2}$, $$ \sum_{k=1}^{n}\binom{n}{k}k^2 = n\sum_{k=1}^{n}\binom{n-1}{k-1}k = n\left(\sum_{k=1}^{n}\binom{n-1}{k-1}+(n-1)\sum_{k=2}^{n}\binom{n-2}{k-2}\right) $$ hence the LHS equals: $$ n\left(2^{n-1}+(n-1)2^{n-2}\right) = n(n+1)2^{n-2}. $$

If you introduce a bronze medal, too, you may easily check that the same argument leads to $$ \sum_{k=1}^{n}\binom{n}{k}k^3 = \binom{n}{1}2^{n-1}+6\binom{n}{2}2^{n-2}+6\binom{n}{3}2^{n-3}=n^2(n+3)2^{n-3}. $$

Solution 2:

This can be seen as two ways of counting the following: You have $n$ numbered, white ping-pong balls. You want to know the number of ways to put some of them in a box, and from those choose one to paint red and one to crush (they might be the same one).

LHS: Either the red ball and the crushed ball are different, or they're the same. If they're different, then there are $n(n-1)$ ways of picking out a red and a crushed ball. Then for the $n-2$ balls that are left, each one can either be put in the bag or not, so that can be done in $2^{n-2}$ ways in total. If you crush the same ball that you paint red, then there are $n$ ways to pick out which ball that is, and $2^{n-1}$ ways to chose which other balls go into the bag. In total, $n(n-1)2^{n-2} + n2^{n-1} = n(n+1)2^{n-2}$.

RHS: First pick $k$ balls. That can be done in $\binom{n}{k}$ ways. Then from those $k$ balls, pick one to paint red, and one to crush. This can be done in $k^2$ ways. Finally, sum over $k$ to get $\sum_{k = 0}^n k^2\binom{n}{k}$.