Question

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}

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`