Let . Show that .
Solution
In the left sum, each term counts the ways to choose a team of people out of , and then designate a captain and a goalkeeper (who can be the same person). The sum thus counts all the ways to form such teams of sizes ranging from 1 to . Let's now proceed with a different counting method. We distinguish two cases. If the captain and the goalkeeper are the same person, we can start by designating this person ( choices). We then choose the rest of the team, in other words, we choose a subset of the remaining people ( choices). This gives us choices. If the captain and the goalkeeper are distinct, we can start by choosing the captain ( choices), then the goalkeeper ( choices), and finally the rest of the team ( choices); this gives us choices. Finally, we have