# Proof of sum of powerset?

Is there already a worst case time complexity proof for the sum of all elements in a power set? I would assume, naively, you have to just add everything, which would run in about 2^n, where n is the size of the set.

For example: A = {1,2,3} Powerset(A) = {{}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3} } Sum(Powerset(A)) = {{} + {1} + {2} + {1 + 2} + {3} + {1 + 3} + {2 + 3} + {1 + 2 + 3} }

I'm defining addition between sets as: A = {1}, B = {2,3}, A + B = {1} + {2 + 3} = 6

• Hint: how many times does $2 \in A$ appear in Powerset($A$)? – Austin Buchanan Mar 12 '14 at 5:32

Hint: If I understand you correctly, you are after $$\sum_{B \subseteq A} \sum_{x \in B} x.$$ Try reversing the order of summation: $$\sum_{B \subseteq A} \sum_{x \in B} x = \sum_{x \in A} \sum_? x,$$ where $?$ is some condition that you will have to come up with. See if that helps you to find a closed formula for the original double sum.