K1) Let $n$ be a strictly positive integer. Maurice writes on the same line all the $2^{n}-1$ non-empty subsets of the set $\{1,2, \ldots, n\}$. Then, below each subset, he writes the product of its elements. Finally, he writes the inverses of the numbers present on the second line and calculates the total. What will be the value of the sum (in terms of $n$) that Maurice will obtain?

Example: for $n=3$, Maurice gets

| $\{1\}$ | $\{2\}$ | $\{3\}$ | $\{1,2\}$ | $\{1,3\}$ | $\{2,3\}$ | $\{1,2,3\}$ | |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :--- |
| 1 | 2 | 3 | $1 \cdot 2=2$ | $1 \cdot 3=3$ | $2 \cdot 3=6$ | $1 \cdot 2 \cdot 3=6$ | |
| $\frac{1}{1}+$ | $\frac{1}{2}+\quad+\frac{1}{3}+$ | $\frac{1}{2}+\quad+\frac{1}{3}+$ | $\frac{1}{6}+$ | $\frac{1}{6}=3$. | | | |
## 1st solution (Louis):

We start by testing small values of $n$ and observe that each time the obtained value is $n$. One therefore poses the hypothesis

$$
H(n): \text { The sum obtained with the set }\{1,2, \ldots, n\} \text { is } n
$$

and we will try to prove by induction that $H(n)$ is true for all natural numbers $n$.

We start with the base case $n=1$. The only non-empty subset of $\{1\}$ is $\{1\}$, and the product of its elements is 1. Thus, the desired sum takes the value 1, and the base case is proven.

For the induction step, assume that $H(n)$ is true and prove $H(n+1)$. We separate the non-empty subsets into two groups. The first group consists of all subsets that do not contain $n+1$, and the second group consists of all subsets that contain $n+1$. For the first group, $H(n)$ proves that the restricted sum for this group is $n$.

We want to prove that for the second group, the restricted sum for this group is 1. By removing the element $n+1$ from each subset of the second group, we obtain all subsets of $\{1,2, \ldots, n\}$ exactly once. By adding $n+1$ to a non-empty subset of $\{1,2, \ldots, n\}$, we multiply the product of its elements by $n+1$. Since we then take the reciprocal, we divide the sum by $n+1$. Using $H(n)$ again, we see that we need to add $\frac{n}{n+1}$. Damnation! We wanted to get 1, but instead, we get $\frac{n}{n+1}$. Is our hypothesis actually false? It seems that it is correct, and the difference comes from the fact that we have not yet considered the set $\{n+1\}$, which adds $\frac{1}{n+1}$ to the sum and thus produces $H(n+1)$. The problem is that this subset clearly belongs to the second group, but by removing the element $n+1$ we get the empty set, so since the sum in $H(n)$ is over non-empty subsets, we must not forget to add the contribution from this subset.

Since both the base case and the induction step have been proven, the principle of induction ensures that $H(n)$ is satisfied for all integers $n$, and thus the value obtained with this sum is $n$.