Prove this $\sum_{S \subseteq\{1, \ldots, n\}}(n-|S|) \pi(S)=(n+1) !\left(\frac{1}{2}+\frac {1}{3}+\ldots+\frac{1}{n+1}\right)$

Question

Set the natural number $n$. For each $S \subseteq\{1, \ldots, n\}$ define $\pi(S)$ as the product of the members of $S$, with the agreement $\pi(\emptyset)=1$. Prove that $$ \sum_{S \subseteq\{1, \ldots, n\}}(n-|S|) \pi(S)=(n+1) !\left(\frac{1}{2}+\frac {1}{3}+\ldots+\frac{1}{n+1}\right) $$

My working: I've worked on the right side so that the result is like this $$(n+1) !\left(\frac{1}{2}+\frac {1}{3}+\ldots+\frac{1}{n+ 1}\right) $$ $$(n+1)!$$$$ \sum_{S \subseteq\{1, \ldots, n\}}(n+1) !\left(\frac{1}{n+1}\right) $$ $$ \sum_{S \subseteq\{1, \ldots, n\}}(n+1)n !\left(\frac{1}{n+1}\right) $$ $$ \sum_{S \subseteq\{1, \ldots, n\}}n ! $$ I don't know if my method is correct or not, please help and correct it

Answer 1

Your approach is not correct because $$\sum_{S \subseteq\{1, \ldots, n\}}(n+1) !\left(\frac{1}{n+1}\right) =\sum_{S \subseteq\{1, \ldots, n\}}n!=n!\sum_{S \subseteq\{1, \ldots, n\}}1=n!\cdot 2^n$$ which is not equal to right-hand side $(n+1) !\left(\frac{1}{2}+\frac {1}{3}+\ldots+\frac{1}{n+ 1}\right)$.

Instead, consider the generating function $$f_n(x)=\sum_{S \subseteq\{1, \ldots, n\}}\pi(S)x^{|S|}$$ then it is easy to verify by induction that $$f_n(x)=\prod_{j=1}^n(1+jx).$$ Indeed $f_1(x)=\pi(\emptyset)x^{|\emptyset|}+\pi(\{1\})x^{|\{1\}|}=1+x$ and for $n>1$, $$\begin{align} f_n(x)&=\sum_{S \subseteq\{1, \ldots, n-1\}}\pi(S)x^{|S|} +\sum_{S \subseteq\{1, \ldots, n-1\}}\pi(S\cup\{n\})x^{|S\cup\{n\}|}\\ &=f_{n-1}(x)+nxf_{n-1}(x)=f_{n-1}(x)(1+nx). \end{align}$$ Hence $$\begin{align} \sum_{S \subseteq\{1, \ldots, n\}}(n-|S|) \pi(S)&= n\sum_{S \subseteq\{1, \ldots, n\}}\pi(S)-\sum_{S \subseteq\{1, \ldots, n\}}|S| \pi(S)\\ &=nf_n(1)-f'_n(1)\\ &=nf_n(1)-f_n(1)\left(\frac{1}{2}+\frac{2}{3}+\dots+\frac{n}{n+1}\right)\\ &=(n+1)!\left(n-\frac{1}{2}-\frac{2}{3}-\dots-\frac{n}{n+1}\right)\\ &=(n+1) !\left(\frac{1}{2}+\frac {1}{3}+\ldots+\frac{1}{n+1}\right). \end{align}$$ Notice that, according to the product rule, $$f'_n(x)=f_n(x)\sum_{j=1}^n\frac{(1+jx)'}{1+jx}=f_n(x)\sum_{j=1}^n\frac{j}{1+jx}.$$

Answer 2

As I mentioned in the comment your idea is not correct.

---

The formula you have to prove resembles Vieta's formulas, so we try with defining polynomial with roots $-1,-2,...-n$

Let $$A(x) = \sum_{S}\pi(S)x^{n-|S|}$$ Clearly $$A(x) = (x+1)(x+2)\cdots (x+n)$$ so $A(1) = (n+1)!$ and $$\ln(A(x)) = \ln (x+1)+\ln(x+2)\cdots \ln(x+n)$$ so $${A'(x)\over A(x)} = {1\over x+1}+{1\over x+2}+\cdots {1\over x+n}$$

So $$A'(1) = A(1)\Big({1\over 2}+{1\over 3}+\cdots {1\over n+1}\Big)$$ $$\boxed{A'(1) = (n+1)!\Big({1\over 2}+{1\over 3}+\cdots {1\over n+1}\Big)}$$

But, on the other hand we have $$A'(x) = \sum_{S}(n-|S|)\pi(S)x^{n-|S|-1}$$ and we are done since $$\boxed{A'(1) = \sum_{S}(n-|S|)\pi(S)}$$