Combinatorial proofs: having a difficult time understanding how to write them out

Can someone explain how combinatorial proofs work? I've included an example questions that's been giving me a hard time. Any insight on the topic would be great.

$$\sum_{k=1}^{n}k{n \choose k} = n2^{n-1}$$

Another one:

$${2n \choose 2} = 2{n \choose 2} + n^2$$

The solution says:

LHS: Pick two people from a pool of n men and n women. RHS: Pick two women, pick two men, and pick one of each.

But I don't see how this applies. How does $n^2$ show that we're picking "one of each?"

Thanks for the help :)

Solution 1:

Most of the simpler combinatorial proofs boil down to showing that two expressions count the same thing, though in two different ways, and therefore have to be equal. Let’s take a look at the identity that I think you actually meant:

$$\sum_{k=1}^nk\binom{n}k=n2^{n-1}\;.\tag{1}$$

Suppose that you have a group of $n$ people, and you want to form a committee of some, possibly all, of those people. You don’t care how big the committee is, but it does have to have a chairman. One way to choose the committee is to pick the chairman, and then decide which subset of the remaining $n-1$ people will be the other members of the committee. There are $n$ possible choices for chairman, and once you’ve picked him, there are $2^{n-1}$ possible subsets of the remaining $n-1$ people to form the rest of the committee. (Yes, I’m including the possibility that the chairman is the only member of the committee.) Thus, there are $n2^{n-1}$ ways to choose the committee and chairman.

On the other hand, we could begin by deciding how big the committee is going to be, then choosing that many people to be on it, and finally choosing one of those to be the chairman. Suppose that we decide to form a committee of $k$ people; there are $\binom{n}k$ ways to choose the $k$ people, and once we’ve done that there are $k$ ways to choose the chairman. Thus, there are $k\binom{n}k$ ways to choose a committee of $k$ of the $n$ people and decide on its chairman. Finally, $k$ can be anything from $1$ through $n$, so the total number of ways to form a committee and choose its chairman is $$\sum_{k=1}^nk\binom{n}k\;.$$

This argument shows that the two sides of $(1)$ are just two different ways of counting the chaired committees that we can form, so they must be equal: they’re counting the same thing.

Added: The righthand side of your second example is very poorly described; here’s what it really is. There are $\binom{n}2$ ways to choose two men. There are another $\binom{n}2$ ways to choose two women. Finally, there are $n^2$ ways to choose one of the $n$ men and one of the $n$ women. Those are the only three possibilities, so altogether there are $2\binom{n}2+n^2$ ways to choose two of the $2n$ people. But of course there are also $\binom{2n}2$ ways, so

$$\binom{2n}2=2\binom{n}2+n^2\;.$$

Solution 2:

The following is to some extent equivalent to Norbert's answer but it uses more sets and fewer formulas. Notice that $\binom nk k$ counts the ways to first choose a $k$-element subset $A$ of $\{1,2,\dots,n\}$ and then choose an element $x$ from $A$. The sum over all $k$ is therefore the number of ways to first choose a subset $A$ of $\{1,2,\dots,n\}$ (with no restriction on its cardinality) and then choose an element $x$ from $A$. That's the same as first choosing the element $x$ arbitrarily from $\{1,2,\dots,n\}$ and then choosing an arbitrary subset of the remaining elements, i.e., a subset of $\{1,2,\dots,n\}-\{x\}$, to constitute the rest of $A$. From this point of view, there are $n$ choices for $x$ and, once $x$ is chosen, $2^{n-1}$ choices for a subset of $\{1,2,\dots,n\}-\{x\}$. Thus, the total number of possibilities is $n2^{n-1}$.