Question

Give a combinatorial proof that if n is a positive integer, then

Answer 1

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

There are $\binom n1=n$ ways of picking the leader, and $\binom{2n-1}{n-1}$ ways of building the rest of the fleet, so there's a total of

$n\dbinom{2n-1}{n-1}$

ways of building such a fleet.

In the other direction, suppose we build a fleet comprising of $k$ X-wings and $n-k$ Y-wings. We have $\binom nk$ ways of picking X-wings and $\binom n{n-k}$ ways of picking Y-wings. Also from the $k$ X-wings we pick 1 to be the leader, which we can do in $\binom k1=k$ ways. So there are

$k\dbinom nk\dbinom n{n-k}$

ways of building such a fleet. But since

$\dbinom nk=\dbinom n{n-k}$, we have

$k\dbinom nk^2$

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

$\displaystyle\sum_{k=1}^nk\binom nk^2$