Consider the set $Q=\{ 1,2,...n \}$. For each $S \subset Q$, let $p(S)$ be the product of elements of $S$, Find the sum of reciprocals $\frac{1}{p(S)}$ for all $S \subset Q$.
I have no idea how to start this. Any hint will be much appreciated.
Asked
Active
Viewed 115 times
3 Answers
1
It should be $n+1$. \begin{eqnarray} \sum_{S\subseteq Q}\frac{1}{p(S)}=\frac{\sum_{S\subseteq Q}p(S)}{n!}=\frac{(1+1)(2+1)\cdots(n+1)}{n!}=n+1 \end{eqnarray}
Alex Fok
- 4,828
-
Oh, I think I understand how to obtain the first equality. After we expand the sum on the LHS, then equate all denominator to $n!$, then notice that numerator is just the summation of $p(S)$, am I right? – Idonknow May 25 '15 at 11:08
-
For the second equality, it is true because of the hint given by Hagen von Eitzen, right? – Idonknow May 25 '15 at 12:07
1
This quantity is $$\left.\prod_{q=1}^n \left(1+\frac{x}{q}\right)\right|_{x=1}$$ which is $$\prod_{q=1}^n \left(1+\frac{1}{q}\right) = \prod_{q=1}^n \frac{q+1}{q} = n+1$$ by telescoping cancellation.
Marko Riedel
- 61,317
0
Hint: Looking at $(1+a)(1+b)(1+c)=1+a+b+c+ab+ac+bc+abc$, what do yo think $(1+1)(1+\frac12)(1+\frac13)\cdots(1+\frac1n)$ expands to?
Hagen von Eitzen
- 374,180
-
$1 + \sum_{k=1}^n{\frac{1}{k}}+$ sum of product of any two fractions + sum of product of any three fractions + ... + product of all fractions? – Idonknow May 25 '15 at 10:44
-