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