Prove the identity
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).