1

I'm clueless as to what this problem even wants me to do. Set theory is not my strength in math.

Problem: There are $2^{3463}-1$ non-empty subsets to $\{\frac{1}{1},\frac{1}{2},\frac{1}{3},...,\frac{1}{3463}\}$. For each such subset, form the product of all elements in the subset. What is the sum of all these products?

aschultz
  • 374
Parseval
  • 6,413
  • It wants you to take ever single possible subset of the sets, multiply the terms of the subset togeter, then add all the $2^{3463 -1}$ such terms together. – fleablood Jul 01 '17 at 16:00
  • Set theory in general and the precise number of those subsets are irrelevant for this problem. Try to write a sum of products as a product of sums. –  Jul 01 '17 at 16:02
  • BTW, for me (non-English native speaker), to read "... subsets to {some set}" instead of "...subsets of {some set}" is slightly disconcerting. Is that correct/common usage? – leonbloy Jul 01 '17 at 16:11

1 Answers1

6

To simplify, generalize:

There are $2^n$ subsets to $S:=\{a_1,\ldots,a_n\}$. For each such subset, form the product of all elements in the subset (with the empty product equal to $1$). What is the sum of all these products?

Let $f(S)$ denote the desired result.

For $n=0$, there is only one subset, the empty subset; its product is $1$, the sum is $1$, so $f(\emptyset)=1$.

Assume we know how to handle the case of $n$ elements. What is the result for $n+1$? Subsets of $\{a_1,\ldots,a_{n+1}\}$ are either subsets of $\{a_1,\ldots,a_{n}\}$ or are subsets of $\{a_1,\ldots,a_{n}\}$ with $a_{n+1}$ added to them. The sum over the products of the first kind is $f(\{a_1,\ldots,a_n\})$. For those of the second kind, each summand gets multiplied by $a_{n+1}$; hence so does the sum. We conclude $$f(\{a_1,\ldots,a_{n+1}\}) =(1+a_{n+1})\cdot f(\{a_1,\ldots,a_{n}\}).$$

From this we readily see (formally: by induction) that $$f(\{a_1,\ldots, a_n\})=\prod_{k=1}^n(1+a_k).$$ Use this formula for the set of the problem statement (and subtract $1$ for the empty set not to be counted). Be ready for a surprise (i.e., first try it with $3463$ replaced by something smaller, for example $5$).

Hagen von Eitzen
  • 374,180