Prove by induction that $\sum_{\varnothing\ne S\subseteq[n]}(\prod S)^{-1}=n$.

104 Views Asked by At

I'm having a hard time visualizing how to prove the following by induction:

For every positive integer $n$, let $[n]$ denote the set $\{1,\ldots,n\}$.

Let $A$ be a set. Use the notation $P(A)$ to indicate the power set of $A$, which consists of all subsets of $A$. For example, if $A=\{0,1\}$, then $P(A)=\big\{\{\},\{0\},\{1\},\{0,1\}\big\}$. Consider $Q(n) = P\big(\{1,\ldots,n\}\big)-\big\{\{\}\big\}$ and use an inductive argument to show that the sum

$$\sum_{S\in Q(n)}\frac1{\prod S}=n\;.$$

For example, the expansion for $n=3$ is

$$\frac11+\frac12+\frac13+\frac1{1\cdot2}+\frac1{1\cdot3}+\frac1{2\cdot3}+\frac1{1\cdot2\cdot3}=3\;.$$

1

There are 1 best solutions below

4
On BEST ANSWER

HINT: Suppose that it’s true for $n$:

$$\sum_{S\in Q(n)}\frac1{\prod S}=n\;.\tag{1}$$

We want to show that it’s true for $n+1$, i.e., that

$$\sum_{S\in Q(n+1)}\frac1{\prod S}=n+1\;.\tag{2}$$

Every non-empty subset of $[n]$ is a non-empty subset of $[n+1]$, so $Q(n)\subseteq Q(n+1)$. What are the other non-empty subsets of $[n+1]$? They’re exactly the subsets of $[n+1]$ that include the integer $n+1$. In other words, they’re the set $\{n+1\}$ and the sets of the form $S\cup\{n+1\}$ with $S\in Q(n)$. This means that

$$\sum_{S\in Q(n+1)}\frac1{\prod S}=\sum_{S\in Q(n)}\frac1{\prod S}+\sum_{S\in Q(n)}\frac1{(n+1)\prod S}+\frac1{n+1}\;;$$

why? Now use the induction hypothesis $(1)$ to show that $(2)$ holds.