Log In

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

  1. XXXX had this to say about that:

    lol

  2. Dinesh had this to say about that:

    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$


{"result":"error", "message":"You can't access this resource as it requires an 'view' access for the website id = 1."}