From Putnam 1996:
Define a selfish set to be a set which has its own cardinality as an element. Find, with proof, the number of subsets of $\{1,2,\ldots,n\}$ which are minimal selfish sets, that is, selfish sets none of whose proper subsets is selfish.
First solution:
We can easily show that a selfish set of length $k$ cannot be minimally selfish if it contains any numbers smaller than $k$. We can conversely show that a selfish set of length $k$ containing only elements greater than or equal to the number $k$ is minimal. Thus we can iterate over the length of the subsets, and simply choose from the remaining numbers to fill the set
\begin{align*}
\sum_{k=0}^n \binom{n-k}{k-1}
\end{align*}
Lastly, notice that $n-k \le k – 1 \implies n+1 \ge 2k$ which means the upper bound can be changed to the floor of $(n+1)/2$.
Second solution:
Let’s consider a inductive solution. Let $s_n$ be the number of minimal selfish set for the set $A_n = \{1,2,\ldots,n\}$. We first note that all minimal selfish set of $A_n$ are also minimal selfish sets in $A_{n+1}$; note that all minimal selfish sets of $A_n$ do not contain the element $n+1$. Thus, the question now is counting how many minimal selfish sets also contains $n+1$.
Actually computing the minimal selfish sets for a few small $n$s suggests that we should be looking for the Fibonacci numbers. Indeed, consider a minimal selfish set $k \subsetneq A_{n-1}$; if we add 1 to each number in $k$, and then append $n+1$, we see that it is also a selfish set, but is it minimal?
Assume that it is not minimal, that is, there exists a strict subset $f$ of $k +1 \cup \{n+1\}$ which is also selfish. The first observation is to note that if $f$ contains $n+1$, then taking $n+1$ out of $f$ then subtracting 1 contradicts the assumption that $k$ is a minimal selfish set. But if $f$ doesn’t contain $n+1$, then removing an arbitrary item and subtracting 1 will again contradict the assumption that $k$ is minimally selfish. We remark that $f$ can be of length of 1 since in the construction, we added 1.
Thus, $f_n = f_{n-1} + f_{n-2}$ and we have that the sum in the first solution is equal to the Fibonacci sequence.