Prove the identity

Printable View

- April 7th 2011, 06:49 AMapple2009Prove the identity using a combinatorial proof
Prove the identity

- April 7th 2011, 09:38 AMveileen
Uhm, what did you try to do?

- April 7th 2011, 11:12 AMapple2009
I try to use a combinatorial proof that both side of the equation count the same thing.

Because I don't know how to try the equation, so I insert the image of it here. (785091c89b91773535544515523d773b.png) - April 7th 2011, 11:25 AMveileen
Write here that attempt and i will help you.

- April 25th 2011, 06:51 PMboldbrandywine
I am also struggling with this same problem, and here is my attempted reasoning after many hours of thought:

Suppose S = {1,2,...,n}; that is, |S|=n. I found it helpful to think about "committees" of people. So let |S| = n be the total number of people. So the LHS counts the total number of all possible committees with a certain unique number of each. Writing out the sum it's easier to see this way: There are C(n,1)=n ways to make a committee of one person, and we only desire 1 of these committees. There are C(n,2) ways to make another committee of two people, we wish to have 2 of these. There are C(n,3) ways to make a third committee of three people; we wish to have 3 of these. And so on and so forth up to our n committees of all n people. Note that the power set of S, P(S), has size |P(S)|=2^n. So we have 1 + ... + n = (n+1)n/2 committees size 1 through n, respectively. But we must divide by (n+1) since the committees are distinct. Thus, by the multiplication principle, we have (2^n)*(n/2) = n*2^(n-1).

Again, this is my reasoning. I feel like there may be a flaw somewhere, and would appreciate any input to make my argument sound better (or even to know if it is valid).