# How can I compute this expression?

I have to understand what is this expression $\sum_{A\subset[n]}\prod_{i\in A}1/i$ where $[n]=\{1,\ldots,n\}$. And then prove it. I was using a very complicated method to understand what this expression is.

The hint of the book is: express the sum as a product.

My method is: $a_n:=\sum_{A\subset[n]}\prod_{i\in A}1/i$ so we have $a_{n+1}=(1/(n+1)+1)a_n$, so if we call $y(x)=\sum_{i=1}^\infty a_nx^n$ we have that $y$ satisfies $y^\prime=(2y+1)/(1-x)$ but I don't know how to continue. I think there is a very very simpler way to compute this expression.

Could any of you help me, please? You can also give me the result without a proof, I will prove it by induction.

-
Well, isn't it $\prod_{i} (1+1/i)$? –  Srivatsan Sep 4 '11 at 21:24
Your recursion is $a_{n+1}/(n+2)=a_n/(n+1)$ and you know that $a_1=2$ hence... –  Did Sep 4 '11 at 21:26

HINT The sum is the same as $$\prod_{i = 1}^{n} \left( 1 + \frac{1}{i} \right).$$ To see why, imagine expanding the above product, and see what the general term looks like.

What's more, the product nicely simplifies by telescopic cancellation.

-
It seems you're right, but I don't understand why $\sum_{S\subset[1]}\prod_{i\in A}1/i=2$? It seems to me that it should be $1$. –  Alex M Sep 4 '11 at 21:44
Ah ah, I understood it, ok thank you for your answer –  Alex M Sep 4 '11 at 21:48
@Alex Yes, the null set can be hiding sometimes :) –  Srivatsan Sep 4 '11 at 21:58

More generally, consider a family $(x_a)$ indexed by $a$ in $A$, and $$S=\sum\limits_{B\subseteq A}\ \prod\limits_{a\in B}x_a.$$ You can show by inspection that $$S=\prod\limits_{a\in A}(1+x_a).$$ Imagine developing $S$ in the following way: write a line of $1$ and just below, a line made of the $x_a$. Then $S$ is the sum of the contributions of all the left-to-right paths in this two-lines array. If a path goes through the bottom position when $a$ is in $B$ and through the upper position otherwise, you get the product $\displaystyle\prod\limits_{a\in B}x_a$.

-

Hint: replace $1/i$ with $a_i$ and try to realize the book's hint on very small $n$, e.g. $n=1,2,3$.

Alternatively, compute the value of the expression for small $n$ and generalize. But then I'm not sure how you'd prove it.

-