Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

3 Answers 3

up vote 2 down vote accepted

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.

share|improve this answer
    
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$.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.