# How to give combinatorial proofs

• Mar 19th 2010, 08:23 AM
swtdelicaterose
How to give combinatorial proofs
I'm trying to make a combotorial proof of this:

${2 \choose 2} + {3 \choose 2} + {4 \choose 2} + ... + {n-1 \choose 2} = {n \choose 3}$

I've proved this using algebra and induction pretty easily. It was just basically expanding it out and cancelling terms. However, I have no idea how to give a combinatorial proof. I've looked at examples in my text book and they all seem to vary and there's no clear way of how to approach a combotorial proof.

Can anyone help get me started?

Thanks!
• Mar 19th 2010, 10:04 PM
wgunther
Trivial for n=3.

$n \choose 3$ is the number of ways to choose subsets of size 3 from a set of size n.

Fix X of cardinality n. Then, for $x\in X$ there are two cases.

Case 1: Count number of subsets containing x. There are $n-1\choose 2$

Case 2: Count the number of subsets not containing x. There are $n-1\choose 3$

By induction, ${n-1\choose 3}={2 \choose 2} + \cdots + {n-2 \choose 2}$

Result follows.
• Mar 20th 2010, 11:06 PM
swtdelicaterose
I actually figured this out by staring at it for 3 hours straight. Can't use induction :(

Anyways, I said that ch(n, 3) is the subset of all three element subsets, which can be divided into further subsets containing highest element n-1, n-2, ... , 3, and each of those subsets you would have to choose 2 more elements that are less than the highest element of that subset. This would give you ch(n-1, 2), ch(n-2, 2), ... , ch(2, 2) since the last subset you would only have a pool of 2 to choose from.

Seems to make sense in my crazy head :o