A subset of $\{1, \ldots, n\}$ is selfish if it contains its own cardinality, and if all its other elements are greater than this cardinality, in other words, if its cardinality is equal to its smallest element. Calculate the number $\mathrm{b}(\mathfrak{n})$ of selfish subsets of $\{1, \ldots, \mathfrak{n}\}$.

## - Solutions of exercises -
The calculation of the first terms suggests that $b(n)=F_{n}$ where $F_{n}$ is the $n$th term of the Fibonacci sequence defined by $F_{0}=0, F_{1}=1$ and $F_{n+2}=F_{n+1}+F_{n}$. We will present two methods to achieve this:

1. With a bijection: The goal is to establish the recurrence relation $b_{n+2}=b_{n+1}+b_{n}$. Let $B(n)$ be the set of selfish subsets of $\{1, \ldots, n\}$. Among the elements of $B(n+2)$, those that do not contain $n+2$ are clearly in bijection with $B(n+1)$. It remains to establish a bijection between the elements of $B(n+2)$ containing $n+2$ and $B(n)$. Given a selfish subset of $\{1, \ldots, n\}$, increase all its elements by 1, and then, to make it selfish again, add $n+2$ (which does not belong to it originally, since all its elements, after increment, do not exceed $n+1$). We obtain a well-defined element of $B(n+2)$ containing $n+2$. Conversely, if we start from an element of $B(n+2)$ containing $n+2$, it does not contain 1, because the only element of $B(n+2)$ containing 1 is $\{1\}$. We can therefore remove $n+2$ and subtract 1 from all its elements, thus obtaining an element of $B(n)$. The two operations we have described are clearly inverses of each other, so we have $b_{n+2}=b_{n+1}+b_{n}$, and the calculation of the first terms concludes.
2. With generating functions: How to "represent" a finite subset of $\mathbb{N}$ as a term of a generating function? If we write it as $\left\{k, k+a_{1}, k+a_{1}+a_{2}, \ldots, k+a_{1}+\ldots+a_{l-1}\right\}$, it suffices to code it using its smallest element $k$, and the successive differences $a_{1}, \ldots, a_{l}$ between the first and second elements, then between the second and third, etc. Thus, the set in question will be "represented" by the term $x^{k} x^{a_{1}} \ldots x^{a_{l}}$, whose degree is equal to its largest element. A selfish set with the smallest term $k$ and cardinality $k$ will have terms that satisfy $l=k$, and will be obtained by expanding the series $x^{k}\left(x+x^{2}+\ldots\right)^{k-1}$. For any integer $m \geqslant k-1$, the coefficient of the term of degree $k+m$ in the expansion of this series is clearly equal to the number of selfish sets of cardinality $k$ and largest element $k+m$. The terms of degree less than $n$ count the selfish sets of cardinality $k$ containing only integers less than $n$, thus corresponding to the selfish subsets of cardinality $k$ of $\{1, \ldots, n\}$. By summing over $k$ to include selfish sets of all sizes, we obtain the series

$$
\begin{aligned}
\sum_{k \geqslant 1} x^{k}\left(x+x^{2}+x^{3}+\ldots\right)^{k-1} & =\sum_{k \geqslant 1} \frac{x^{2 k-1}}{(1-x)^{k-1}} \\
& =x \sum_{k \geqslant 1}\left(\frac{x^{2}}{1-x}\right)^{k-1} \\
& =x \frac{1}{1-\frac{x^{2}}{1-x}} \\
& =\frac{x(1-x)}{1-x-x^{2}}
\end{aligned}
$$

It now suffices to extract the sum of the first $n$ coefficients of this series, by taking the term of degree $n$ of

$$
\frac{1}{1-x} \times \frac{x(1-x)}{1-x-x^{2}}=\frac{x}{1-x-x^{2}}
$$

And in this last series, we recognize the generating function of $F_{n}$.

## 4 Polynomials