Give a combinatorial proof that if n is a positive integer, then
\sum_{k=1}^{n} k\binom{n}{k}^2= n\binom{2n-1}{n-1}

The Empire is attacking a Rebel base that is stocked with X-wings and Y-wings. The Rebels need to build a fleet consisting of ships (with at least 1 X-wing), to be led by 1 pilot in an X-wing.

There are ways of picking the leader, and ways of building the rest of the fleet, so there's a total of

ways of building such a fleet.

In the other direction, suppose we build a fleet comprising of X-wings and Y-wings. We have ways of picking X-wings and ways of picking Y-wings. Also from the X-wings we pick 1 to be the leader, which we can do in ways. So there are

ways of building such a fleet. But since

, we have

ways of building the fleet with these specifications. Sum over all possible values of ,