Let $H=\{2,3,4,\dots,n+1\}$. Show that $\sum_{\emptyset \neq S\subset H}\prod_{i\in S}\frac{1}{i}=n/2$.

Question

Let $H:=\{2,3,4,\dots,n+1\}$. Show that $$\sum_{\emptyset \neq S\subset H}\prod_{i\in S}\frac{1}{i}=n/2.$$ For example, with $n=3$, we have $\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{2\cdot 3}+\frac{1}{2\cdot 4}+\frac{1}{3\cdot 4}+\frac{1}{2\cdot 3\cdot 4}=\frac{3}{2}.$

I tried induction but it leads to too many terms to deal with for the inductive hypothesis. How do I prove this, with induction or otherwise?

score 2 · Accepted Answer · answered Jul 29 '21 at 06:25

2

Hint: In general $$\sum_{\emptyset\ne S \subset H} \prod_{i\in S} a_i = \prod_{i\in H} (1+ a_i) - 1$$

answered Jul 29 '21 at 06:25

orangeskid

53,909

How do you arrive at this identity? – tmaj Jul 29 '21 at 06:37
@tmaj: you can prove it by induction on $|H|$. It's worth checking it for $H$ of small cardinality. – orangeskid Jul 29 '21 at 06:53

Let $H=\{2,3,4,\dots,n+1\}$. Show that $\sum_{\emptyset \neq S\subset H}\prod_{i\in S}\frac{1}{i}=n/2$.

1 Answers1