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

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,

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

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

3. 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:

1. Just $\{n+1\}$
2. a non-empty subsets of the first $n$ positive integers together with $n+1$.
3. 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:

1. $\frac{1}{n+1}$
2. $n$
3. $\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.

Answer 1

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$$

Answer 2

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.$$