Exercise 12. On a line, Timothé writes all non-empty subsets of $\{1, \ldots, \boldsymbol{n}\}$, numbering $2^{n}-1$. Below, he writes the product of the elements of each of these subsets. Still below, he writes the inverses of each of these quantities, then adds the numbers on the last line. What is the number obtained by Timothé?
Solution to Exercise 12 Let $a_{n}$ be the number of Timothé. We start by noting that $a_{1}=1$. Then, we seek to express $a_{n+1}$ in terms of $a_{n}$. For this, we observe that there are 3 types of non-empty subsets of $\{1, \ldots, n+1\}$: those that do not contain $n+1$, those that contain $n+1$ and something else, and $\{n+1\}$. If we consider a subset of the first type, its contribution will be the same as with $n$ elements, and the total contribution of subsets of the first type is therefore $a_{n}$. If we consider a subset of the second type, we can write it as $Y=n+1 \cup X$, with $X \subset\{1, \ldots, n\}, X \neq \emptyset$. When we multiply the elements of $Y$, we get $n+1$ times what we get by multiplying those of $X$, and thus, by inverting and factoring, the contribution of subsets of the second type is $\frac{a_{n}}{n+1}$. Finally,

$$
a_{n+1}=a_{n}+\frac{a_{n}}{n+1}+\frac{1}{n+1}
$$

By testing with small values of $n$, we conjecture that $a_{n}=n$. We prove this by induction using the formula we have found. We already have $a_{1}=1$. If we then assume that $a_{n}=n$ for some $n \geqslant 1$, we find that

$$
a_{n+1}=n+\frac{a_{n}}{n+1}+\frac{1}{n+1}=n+\frac{n}{n+1}+\frac{1}{n+1}=n+1
$$

which ensures the heredity and completes the induction.

Thus $a_{n}=n$ for all $n$.

Graders' Comments: The exercise is very well solved.