# 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 :)

-
Do you mean $\sum k\binom{n}{k}$? –  Thomas Belulovich Nov 14 '12 at 0:58
Yes, sorry, I do. –  user1038665 Nov 14 '12 at 1:04
about "one of each": $n^2 = {n\choose 1}{n\choose 1}$. –  Hendrik Jan Nov 14 '12 at 1:16

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 sum, 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 committed 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\;.$$

-
Seems you beat me to it, +1 –  Jean-Sébastien Nov 14 '12 at 1:13

To provide a direct proof by counting, assuming the correction $\sum k \binom{n}{k}$:

Consider the problem of choosing a subset of $[n] = \{1,2,\dots,n\}$ with a distinguished element. We can count this directly: first pick the distinguished element from $[n]$ -- there are $n$ choices.. This leaves $n-1$ elements to choose from to make the remainder of the set, and there are $2^{n-1}$ ways to make this choice. So we have $n2^{n-1}$ ways of choosing a subset with distinguished element.

Or, we can enumerate based on $k$, the number of elements in the set. For each $k$, there are $\binom{n}{k}$ ways to choose a subset of $[n]$ of size $k$. For each such set, there are $k$ ways to make a choice of distinguished element. Summing on $k$ gives $\sum_{k=1}^n k \binom{n}{k}$.

So now we've given two ways to count the number of subsets of $n$ with distinguished element. These must be equal. So $\sum_{k=1}^n k \binom{n}{k} = n2^{n-1}$.

-

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}$.

-
It seems lots of people wrote essentially what I did while I was typing. I need to learn to type faster. –  Andreas Blass Nov 14 '12 at 1:12
Yup me too apparently –  Jean-Sébastien Nov 14 '12 at 1:14

This is more engeniering than mathematical approach. For difficult combinatorial identities this may be the only possible solution. Consider well known binomial formula $$(1+x)^n=\sum\limits_{k=0}^n {n \choose k} x^k$$ Differentaite it with respect to $x$ to get $$n(1+x)^{n-1}=\sum\limits_{k=0}^n{n\choose k}k x^{k-1}$$ After substitution $x=1$ we see that $$n 2^{n-1}=\sum\limits_{k=0}^n{n\choose k}k=\sum\limits_{k=1}^n{n\choose k}k$$

-
How can we get a solution without doing an algebraic proof? That is, describing the left-hand and right-hand sides to show that the two are equal? –  user1038665 Nov 14 '12 at 1:05

You can see it as the number of ways to select a subset of a set of $n$ elements while marking one of the selected elements. For a subset of size $k$, there are $k$ ways to mark $1$ element, so you get the left part $\sum_{i=0}^{n}k\binom{n}{k}$. You can also see this the other way around : chose any of the elements of the set as the marked one, and then pick any other. You can then mark $n$ elements, and for each element marked, you can either take or not the remaining ones, which leads to the right side $n2^{n-1}$.

As for your second question, if you have $n$ men and $n$ women, in how many ways can you choose $1$ man and $1$ woman ? Well for each man, you can chose any of the $n$ women, which leads to $n^2$.

-

Imagine you want to form a team with $n$ persons. The team can be of any size from $1$ to $n$, but it needs a captain. Let's count the left-hand side way:

We sepatate depending on the number of persons in the team. If there are $k$ persons in the team, you choose them with $n\choose k$, and for each such team, pick a captain, $k\choose 1$$=k ways. Sum over all k=1\ldots n to get the LHS. On the right hand side, choose a captain first, in n\choose 1$$=$n ways, and then make up your team with the $n-1$ remaining persons. Each one can either be part of the team or not, which gives $2^{n-1}$ teams.

-