0

Suppose you have the set $\{1,...,n\}$. What is the sum of the sum of elements of all subsets of it?

I have the following reasoning: each number $1 \leq i \leq n$ appears in $\sum_{k=1}^n {n \choose {k-1}} = 2^n - 1$ subsets, and therefore we can just do a sum over $i\cdot(2^n - 1)$ for all $i=1,...,n$. However, I am not sure that the way I have taken is correct.

Will be glad for some hints.

TheNotMe
  • 4,841

1 Answers1

1

Each number occurs in $2^{n-1}$ subsets. Indeed: pick a number $k$. Then a half of the subsets contain $k$ and the other half do not.

An example:

$$0+1+2+3+(1+2)+(1+3)+(2+3)+(1+2+3)=(1+2+3)\cdot 2^2$$

ajotatxe
  • 65,084
  • Why is my combinatorial way of calculating that is wrong? suppose the subset size is $k$, then you have to choose some other $k-1$ elements for the subset and then have $i$ in it as well, yielding $\sum_{k=1}^n {n \choose {k-1}}$ – TheNotMe Dec 19 '17 at 15:15
  • 1
    The other $k-1$ elements are to be chosen from a set of $n-1$ (because the number $i$ is already chosen). The correct sum would be $$\sum_{k=1}^{n}\binom{n-1}{k-1}=\sum_{k=0}^{n-1}\binom{n-1}k=2^{n-1}$$ – ajotatxe Dec 19 '17 at 15:16
  • Thank you for pointing the mistake. – TheNotMe Dec 19 '17 at 15:21