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!
Best Answer
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$.