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{array}{rl}{a}_{2m+2}& =C_{2m+2}^1+C_{2m+1}^2+\cdots +C_{m+2}^{m+1}\\ & =(C_{2m+1}^1+C_{2m+1}^0)+(C_{2m}^2+C_{2m}^1)+\cdots +(C_{m+1}^{m+1}+C_{m+1}^m)\\ & =(C_{2m+1}^1+C_{2m}^2+\cdots +C_{m+1}^{m+1})+(C_{2m}^1+C_{2m-1}^2+\dots \\ & +C_{m+1}^m)+C_{2m+1}^0\\ & =a_{2m+1}+a_{2m}+1.\end{array}$$

If $n$ is odd, $n=2m-1$, then $$\begin{array}{rl}{a}_{2m+1}& =C_{2m+1}^1+C_{2m}^2+\cdots +C_{m+2}^m+C_{m+1}^{m+1}\\ & =(C_{2m}^1+C_{2m}^0)+(C_{2m-1}^2+C_{2m-1}^1)+\cdots +(C_{m+1}^m+C_{m+1}^{m-1})+C_m^m\\ & =(C_{2m}^1+C_{2m-1}^2+\cdots +C_{m+1}^m)+(C_{2m-1}^1+C_{2m-2}^2+\dots \\ & +C_{m+1}^{m-1}+C_m^m)+C_{2m}^0\\ & =a_{2m}+a_{2m-1}+1.\end{array}$$

In summary, the equality $a_{n+2}=a_{n+1}+a_n+1$ holds for all positive integers $n.<br/><br/>---<br/><br/>\ast \ast Alternativesolution.\ast \ast <br/><br/>If$n=1$,thereisonlyonegoodsetofdegree$1$,namely$\{1\}$,so$a_1 = 1$.If$n=2$,thenthereareonlytwogoodsetsofdegree$2$:$\{1\}, \{2\}$,so$a_2 = 2$.Recallthat$a_n, a_{n+1}$arethenumbersofthenon-emptygoodsubsets$A$of$\{1, 2, \dots, n\}$and$\{1, 2, \dots, n+1\}$,respectively,satisfying$|A| \le \min_{x \in A} x$.<br/><br/>Considerthecase$n + 2$:Foranynon-emptygoodset$A$ofdegree$n + 2$,$A$isasubsetof$\{1, 2, \dots, n + 2\}$,thenwehavethefollowingthreecases:<br/><br/>a.$A$doesnotcontaintheelement$n + 2$;b.$A$contains$n + 2$,andhasatleast$2$elements;c.$A = \{n + 2\}$.<br/><br/>Inthefollowing,wefocusonthenumberofgoodsetsoftypes(a)and(b).Foranygoodset$A$in(a),itfollowsfrom$|A| \le \min_{x \in A} x$and$\max_{x \in A} x \le n + 1$that$A$isagoodsetofdegree$n + 1$.Conversely,anygoodsetofdegree$n + 1$isalsoagoodsetofdegree$n + 2$,therefore,thereareexactly$a_{n+1}$goodsetsoftype(a).<br/><br/>Foranygoodset$A = \{a_1, a_2, \dots, a_k, n+2\}$ofdegree$n+2$oftype(b),where$a_1 < a_2 < \dots < a_k < n+2$.As$a_1 = \min_{x \in A} x \ge |A| \ge 2$,onecanconsiderthenon-emptyset$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'$isagoodsetofdegree$n$.Conversely,anygoodsetofdegree$n$canberepresentedintheform$A' = \{a_1 - 1, a_2 - 1, \dots, a_k - 1\}$,where$A = \{a_1, a_2, \dots, a_k, n+2\}$isagoodsetofdegree$n+2$oftype(b),sothecorrespondenceisone-to-onebetween$A$and$A'$,andthereareexactly$a_n$goodsetsofdegree$n+2$oftype(b).<br/><br/>Accordingtothediscussiononthenumberofgoodsetsoftypes(a),(b)and(c),wehave$a_{n+2} = a_{n+1} + a_n + 1$.$\square$