Find a combinatorial argument for the following binomial identity: $$n(n+1)2^{n-2} = \sum_{k=1}^{n}k^2\binom{n}{k} .$$
Algebraic proofs can be found at Can $n(n+1)2^{n-2} = \sum_{i=1}^{n} i^2 \binom{n}{i}$ be derived from the binomial theorem? , and a related identity at $\sum_{k=1}^m k(k-1){m\choose k} = m(m-1) 2^{m-2}$ .
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}. $$
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}$.
This is a little convoluted, but I decided to set myself the challenge of redesigning Jack D'Aurizio's medalist-selection process so that it consists of $n$ steps, where the first step has $n$ possibilities, the second step has $n+1$ possibilities, and the remaining steps have $2$ possibilities each. (Note that this only makes sense if $n\ge2$.)
Imagine the $n$ people sitting a circle. The first step is to pick a gold medalist; this obviously has $n$ possibilities.
In preparation for the second step, insert an empty chair between the gold medalist and the person sitting to his/her immediate left; for convenience of exposition, let's call the gold medalist Alex, and the person on the other side of the empty chair Bernie.
Now choose one of the $n+1$ chairs. If the chosen chair is the empty one, then Bernie is given a bronze medal and Alex is given the silver; if the chosen chair is occupied by Alex, then Bernie is not given a bronze and Alex is given the silver; in all other cases, the occupant of the chosen chair is given the silver medal.
In preparation for the remaining steps, we remove two people from the circle, namely Alex and the silver medalist, along with Bernie if Alex is the silver medalist. This leaves $n-2$ people, and we now simply decide for each if they are given a bronze medal or not.
Remarks: The only thing I've borrowed, really, from Jack's (excellent) answer is the notion of giving out gold and silver medals to make things concrete. (I added bronze medals to sharpen the concrete imagery a bit.) Arthur's (also excellent) answer is essentially the same as Jack's; it looks like they were composed more or less simultaneously. Mainly it occurred to me that both answers essentially give a combinatorial proof that $\sum k^2{n\choose k}=n(n-1)2^{n-2}+n2^{n-1}$ followed by the (more or less trivial) algebraic identity $n(n-1)2^{n-2}+n2^{n-1}=n(n+1)2^{n+2}$; I just wanted to see if you could eliminate the algebraic middle man.
