Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sorry in advance, as I suspect I lack both the proper terms and the proper notation for the problem I have, but I'll try to be clear.

If I have a set $S = \{1,2,3\}$, I figured out that the summation of the "subset sums" of its power set is $\sum_i S_i \times 2^{|S| - 1}$.

For instance, as $P(S) = \{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}$, this sum is $0+1+2+3+3+4+5+6=24$, i.e. $6 \times 2^2$.

Now I'd like to find a formula for the related summation where instead of summing the "subset sums", I sum 2 to their power: $2^0+2^1+2^2+2^3+2^3+2^4+2^5+2^6=135$.

I tried to reverse-engineer this formula for a long time, using many examples, but it completely eludes me.. Thanks for any help or clarification!

share|improve this question
1  
Your formula for the sum is correct. The simple justification is that there are $2^{|S|}$ subsets and each element is in half of them, so the element contributes $2^{|S|-1}$ times to the sum. –  Ross Millikan Nov 15 '12 at 19:05

1 Answer 1

up vote 6 down vote accepted

Denoting your summation with $f(S)$, we have the follwoing facts: $$f(\emptyset)=1$$ and if $S':=S\setminus\{x\}$ for some $x\in S$, then $$ f(S) = f(S')\cdot(1+2^x)$$ because the subsets of $S$ can be partitioned into those not containing $x$ (giving $f(S')$) and those containing $x$ (where each sorresponding summand is multiplied by $2^x$). Therefore, one readily sees that $$f(S)=\prod_{x\in S}(1+2^x).$$ In your example: $(1+2^1)(1+2^2)(1+2^3)=3\cdot 5\cdot 9=135$.

share|improve this answer
    
Many thanks! I am puzzled and greatly impressed by your speed.. is that a reasoning that you made on the fly, or you had somehow thought about a related problem before? –  cjauvin Nov 15 '12 at 19:19
    
Hm, both I guess. –  Hagen von Eitzen Nov 15 '12 at 19:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.