Thread: How to give combinatorial proofs

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



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!

Trivial for n=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 there are two cases.

Case 1: Count number of subsets containing x. There are

Case 2: Count the number of subsets not containing x. There are

By induction,

Result follows.

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