3
$\begingroup$

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.

  • 0
    Your recursion is $a_{n+1}/(n+2)=a_n/(n+1)$ and you know that $a_1=2$ hence...2011-09-04

3 Answers 3

0

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.

3

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$.

2

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.

  • 0
    @Alex Yes, the null set can be hiding sometimes :)2011-09-04