## Summing products

Posted on: February 28th, 2013 by
2

Consider nonempty subsets of the set {1,2,...,N}. For each such subset we can compute the product of the reciprocals of each member. Find the sum of all such products.
via Australian Mathematical Society gazette puzzle corner

#### 2 Responses to Summing products

Answer is N. By multiplying and dividing by N!, we can write the sum as $\frac{1}{N!} \sum \prod_{a \in A^c} a$, where the sum ranges over all non-empty subsets of {1,..,N}. Rewriting the sum, we get $\frac{1}{N!} \sum_{A \subset \{1,...,N\}} \prod_{a \in A} a$.
Claim is that the sum satisfies the recursion $f(N) = N f(N-1) + f(N-1) + (N-1)!$. This can be seen by splitting the sum into two sets, one over all subsets that contain $N$ (this will give you N f(N-1)$and other over the remaining subsets (the set$\{1,...,N-1\}$will give the (N-1)! and the others will give$f(N-1)$). Once we have the recursion, we can verify that the solution is$f(N) = N \cdot N!$and therefore, the desired sum is simply$N\$