# Thread: How to give combinatorial proofs

1. ## How to give combinatorial proofs

I'm trying to make a combotorial proof of this:

$\displaystyle {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!

2. Trivial for n=3.

$\displaystyle 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 $\displaystyle x\in X$ there are two cases.

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

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

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

Result follows.

3. 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