Show that $\sum_{\{a_1, a_2, \dots, a_k\}\subseteq\{1, 2, \dots, n\}}\frac{1}{a_1*a_2*\dots*a_k} = n$ Question:
Show that $$\sum_{\{a_1, a_2, \dots, a_k\}\subseteq\{1, 2, \dots, n\}}\frac{1}{a_1*a_2*\dots*a_k} = n$$
(Here the sum is over all non-empty subsets of the set of the $n$ smallest positive integers.)

I made an attempt and then encountered an inconsistency with the
  answer key which is detailed at the very bottom.

My Attempt:
$n=1$, there's only one non-empty subset $\{1\}$, hence,
$$\frac{1}{1} = 1$$
Let the proposition in the question be $P(n)$. Suppose $P(n)$ is true, show that $P(n)\rightarrow P(n+1)$ is true,
$$P(n) = \sum_{\{a_1, a_2, \dots, a_k\}\subseteq\{1, 2, \dots, n\}}\frac{1}{a_1*a_2*\dots*a_k}=n$$
$P(n+1)$ would mean, I add another integer $n+1$ to the set, the change to the possible subsets are divided into 3 cases,


*

*Subset of only $\{n+1\}$.

*Subsets of all positive integers containing $\{n+1\}$.

*Subsets of all positive integers not containing $\{n+1\}$.
First case, just $$\frac{1}{n+1}$$,
Second case, is $$\frac{P(n)}{n+1} = \frac{n}{n+1}$$,
Third case, by inductive hypothesis is just $n$,
Thus, adding them all we get, $$\frac{1}{n+1} + \frac{n}{n+1} + n = n + 1$$, completing the proof.
Problem:
The following are cases in the answer key:


*

*Just $\{n+1\}$

*a non-empty subsets of the first $n$ positive integers together with $n+1$.

*a non-empty subset of the first $n$ positive integers.


(I've rearrange the cases so they all correspond to the ordering I gave in my Inductive Step). The following are the sub of the cases in the answer key:


*

*$\frac{1}{n+1}$

*$n$

*$\frac{n}{n+1}$


As one can tell, case 1 is the same but case 2 and 3 is switch with respect to mine. What did I do wrong, it is unlikely that the textbook is wrong.
 A: Let$$A(n)=\sum_{\{a_1, a_2, \dots, a_k\}\subseteq\{1, 2, \dots, n\}}\frac{1}{a_1*a_2*\dots*a_k}$$
Note that $$\sum_{\{a_1, a_2, \dots, a_k\}\subseteq\{1, 2, \dots, n\}}1=2^n-1$$
Let $\mathcal{A_n}=\{\{a_1, a_2, \dots, a_k\}:\{a_1, a_2, \dots, a_k\}\subseteq\{1, 2, \dots, n\}\}$.
$\mathcal{A_{n+1}}=\mathcal{A_n}+\{n+1,\mathcal{A_n}\}+\{n+1\}$ (here $+$ denotes as disjoint unions and $\{n+1,\mathcal{A_n}\}=$the set of union of $\{n+1\}$ and every element of $\mathcal{A_n}$). 
Thus we have the recursion relation $(n+1)A(n+1)=(n+2)A(n)+1$ with $A(1)=1, A(2)=2$.
Now we can use induction by taking $A(n)=n$ gives us $(n+1)A(n+1)=(n+1)^2\Rightarrow A(n+1)=n+1$.
Hence $$\sum_{\{a_1, a_2, \dots, a_k\}\subseteq\{1, 2, \dots, n\}}\frac{1}{a_1*a_2*\dots*a_k}=n$$
A: We get from first principles that this sum is given by
$$\sum_{k=1}^n [z^k] \prod_{q=1}^n \left(1+\frac{z}{q}\right)
\\ = \frac{1}{n!} \sum_{k=1}^n [z^k] \prod_{q=1}^n \left(z+q\right)
\\ = - 1 + \frac{1}{n!} \sum_{k=0}^n [z^k] \prod_{q=1}^n \left(z+q\right).$$
This is
$$-1 + \frac{1}{n!} \prod_{q=1}^n \left(1+q\right) =
- 1 + \frac{1}{n!} (n+1)! = n.$$
