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

Subscribe & Follow

via Australian Mathematical Society gazette puzzle corner

lol

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$