We will use induction: denote $S_n= \sum_{S \subseteq \{1,2..,n\}} \frac{\sigma(S)}{\pi(S)}$ First step: $S_1=1 = 1^2 +2*1 -(1)*(1+1)$ Inductive step: Assume that $S_n= n^2+2n - \left( 1+ \frac 12 + \frac 13+ ... \frac 1n \right) (n+1)=$ $= (n+1)^2 - \left ( 1+ \frac 12 + \frac 13+ ... \frac 1n + \frac 1{n+1} \right) (n+1)$ Now let's see what is $S_{n+1}$. $S_{n+1}=\sum_{S \subseteq \{1,2..,n+1\}} \frac{\sigma(S)}{\pi(S)} = \sum_{S \subseteq \{1,2..,n\}} \frac{\sigma(S)}{\pi(S)}+\sum_{S \subseteq \{1,2..,n\}} \frac{\sigma(S\cup\{n+1\})}{\pi(S\cup\{n+1\})}+ \frac{\sigma(\{n+1\})}{\pi(\{n+1\})}$ Now $\frac{\sigma({n+1})}{\pi({n+1})}=1$ and $\sum_{S \subseteq \{1,2..,n\}} \frac{\sigma(S\cup\{n+1\})}{\pi(S\cup\{n+1\})}=$ $\sum_{S \subseteq \{1,2..,n\}} \frac{\sigma(S)+ n+1}{(n+1)\pi(S)} = \frac 1{n+1} S_n + \sum_{S \subseteq \{1,2..,n\}} \frac 1{\pi(S)}$ But we can see that $\sum_{S \subseteq \{1,2..,n\}} \frac 1{\pi(S)} = \prod_{i=1} ^n \left(1+\frac 1i\right) - 1 = \prod_{i=1}^n \frac{i+1}i -1= (n+1) - 1$ And so we have that: $S_{n+1} = \frac{n+2}{n+1} S_n + (n+1) -1 +1 =$ $=(n+2)(n+1) - \left ( 1+ \frac 12 + \frac 13+ ... \frac 1n + \frac 1{n+1} \right) (n+2) + (n+2) -1 =$ $= (n+2)^2 - \left ( 1+ \frac 12 + \frac 13+ ... \frac 1{n+1} + \frac 1{n+2} \right) (n+2)$ That's it! Do you have a combinatorial proof?

Let $ F(x) = \prod_{k = 1}^{n} \left( 1 + \frac {x^k}{k} \right)$; then the desired quantity is $ F'(1) $. Logarithmic differentiation gives $ \ln F = \sum_{k = 1}^{n} \ln \left( 1 + \frac {x^k}{k} \right) \Rightarrow$ $ \frac {F'(x)}{F(x)} = \sum_{k = 1}^{n} \frac {kx^{k - 1}}{k + x^k}$ which gives $ \frac {F'(1)}{F(1)} = \sum_{k = 1}^{n} \frac {k}{k + 1} = n + 1 - H_{n + 1}$. On the other hand, obviously $ F(1) = n + 1$. This gives the desired result.

t0rajir0u wrote: Let $ F(x) = \prod_{k = 1}^{n} \left( 1 + \frac {x^k}{k} \right)$; then the desired quantity is $ F'(1) - 1$. Logarithmic differentiation gives $ \ln F = \sum_{k = 1}^{n} \ln \left( 1 + \frac {x^k}{k} \right) \Rightarrow$ $ \frac {F'(x)}{F(x)} = \sum_{k = 1}^{n} \frac {kx^{k - 1}}{k + x^k}$ which gives $ \frac {F'(1)}{F(1)} = \sum_{k = 1}^{n} \frac {k}{k + 1} = n + 1 - H_{n + 1}$. On the other hand, obviously $ F(1) = n + 1$. This gives the desired result. Wow, this is awesome! Here's another proof:

$ $