China Western Mathematical Olympiad

Let $A$ be a good set of degree $n$, and $|A| = k$, then $\min_{x \in A} x \ge k$, so $A \subseteq \{k, k+1, \dots, n\}$. Hence the number of good sets of degree $n$ with $k$ elements is $C_{n-k+1}^k$. It follows that $a_n = \sum_{k=1}^{\lfloor \frac{n+1}{2} \rfloor} C_{n-k+1}^k = C_n^1 + C_{n-1}^2 + C_{n-2}^3 + \dots$.

If $n$ is even, $n = 2m$, then
$$\begin{align*} a_{2m+2} &= C_{2m+2}^1 + C_{2m+1}^2 + \dots + C_{m+2}^{m+1} \\ &= (C_{2m+1}^1 + C_{2m+1}^0) + (C_{2m}^2 + C_{2m}^1) + \dots + (C_{m+1}^{m+1} + C_{m+1}^m) \\ &= (C_{2m+1}^1 + C_{2m}^2 + \dots + C_{m+1}^{m+1}) + (C_{2m}^1 + C_{2m-1}^2 + \dots \\ &\qquad\qquad + C_{m+1}^m) + C_{2m+1}^0 \\ &= a_{2m+1} + a_{2m} + 1. \end{align*}$$

If $n$ is odd, $n = 2m - 1$, then
$$\begin{align*} a_{2m+1} &= C_{2m+1}^1 + C_{2m}^2 + \dots + C_{m+2}^m + C_{m+1}^{m+1} \\ &= (C_{2m}^1 + C_{2m}^0) + (C_{2m-1}^2 + C_{2m-1}^1) + \dots + (C_{m+1}^m + C_{m+1}^{m-1}) + C_m^m \\ &= (C_{2m}^1 + C_{2m-1}^2 + \dots + C_{m+1}^m) + (C_{2m-1}^1 + C_{2m-2}^2 + \dots \\ &\qquad + C_{m+1}^{m-1} + C_m^m) + C_{2m}^0 \\ &= a_{2m} + a_{2m-1} + 1. \end{align*}$$

In summary, the equality $a_{n+2} = a_{n+1} + a_n + 1$ holds for all positive integers $n.

If $n=1$, there is only one good set of degree $1$, namely $\{1\}$, so $a_1 = 1$.
If $n=2$, then there are only two good sets of degree $2$: $\{1\}, \{2\}$, so $a_2 = 2$.
Recall that $a_n, a_{n+1}$ are the numbers of the non-empty good subsets $A$ of $\{1, 2, \dots, n\}$ and $\{1, 2, \dots, n+1\}$, respectively, satisfying $|A| \le \min_{x \in A} x$.

Consider the case $n + 2$: For any non-empty good set $A$ of degree $n + 2$, $A$ is a subset of $\{1, 2, \dots, n + 2\}$, then we have the following three cases:

a. $A$ does not contain the element $n + 2$;
b. $A$ contains $n + 2$, and has at least $2$ elements;
c. $A = \{n + 2\}$.

In the following, we focus on the number of good sets of types (a) and (b). For any good set $A$ in (a), it follows from $|A| \le \min_{x \in A} x$ and $\max_{x \in A} x \le n + 1$ that $A$ is a good set of degree $n + 1$. Conversely, any good set of degree $n + 1$ is also a good set of degree $n + 2$, therefore, there are exactly $a_{n+1}$ good sets of type (a).

For any good set $A = \{a_1, a_2, \dots, a_k, n+2\}$ of degree $n+2$ of type (b), where $a_1 < a_2 < \dots < a_k < n+2$. As $a_1 = \min_{x \in A} x \ge |A| \ge 2$, one can consider the non-empty set $A' = \{a_1 - 1, a_2 - 1, \dots, a_k - 1\}$, where $1 \le a_1 - 1 < a_2 - 1 < \dots < a_k - 1 < n+1$, and $A'$ satisfies $|A'| = |A| - 1 \le a_1 - 1 = \min_{x \in A'} x$, hence $A'$ is a good set of degree $n$. Conversely, any good set of degree $n$ can be represented in the form $A' = \{a_1 - 1, a_2 - 1, \dots, a_k - 1\}$, where $A = \{a_1, a_2, \dots, a_k, n+2\}$ is a good set of degree $n+2$ of type (b), so the correspondence is one-to-one between $A$ and $A'$, and there are exactly $a_n$ good sets of degree $n+2$ of type (b).

According to the discussion on the number of good sets of types (a), (b) and (c), we have $a_{n+2} = a_{n+1} + a_n + 1$. $\square$