Maths Olympiad Prep

Library / /383 of 520

Combinatorics Difficulty 5.9 AIME, harder Prove it

Let n1n \geqslant 1. Show that k=1n(nk)k2=n(n+1)2n2\sum_{k=1}^{n}\binom{n}{k} k^{2}=n(n+1) 2^{n-2}.

Solution

In the left sum, each term counts the ways to choose a team of kk people out of nn, 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 nn. 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 (nn choices). We then choose the rest of the team, in other words, we choose a subset of the remaining n1n-1 people (2n12^{n-1} choices). This gives us n2n1n 2^{n-1} choices. If the captain and the goalkeeper are distinct, we can start by choosing the captain (nn choices), then the goalkeeper (n1n-1 choices), and finally the rest of the team (2n22^{n-2} choices); this gives us n(n1)2n2n(n-1) 2^{n-2} choices. Finally, we have

n2n1+n(n1)2n2=n(n+1)2n2 n 2^{n-1}+n(n-1) 2^{n-2}=n(n+1) 2^{n-2}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.