Let $H=\{2,3,4, \dots , n\}$. Find a recurrence relation that involves the following number: $\displaystyle \sum_{G\subseteq H}\frac{1}{\prod_{x\in G}}$, where $G\not = \{\}$
If $H=\{2\}$, let $S_2$ be the sum. If $H=\{2,3\}$ let $S_3$ be the sum, and so on.
Now, I'm trying to find a recurrence relation, and from looking at small cases it's pretty obviously $S_n = S_{n-1} + \frac{1}{n}(1 + S_{n-1})$. But how exactly do I prove that this is a valid recurrence relation for all $n$?
Use that $$ \sum_{G\subseteq H}=\sum_{G\subseteq H\atop n\in G}+\sum_{G\subseteq H\atop n\notin G}$$