若非空集合 $A\subset \{1,2,3,\ldots,n\}$ 足 $|A|\leqslant \min_{x\in A}x$．则称 $A$ 为 $n$ 级好集合．记 $a_n$ 为 $n$ 级好集合的个数．
求证：对一切正整数 $n$，都有 $a_{n+2}=a_{n+1}+a_{n}+1$．
求证：对一切正整数 $n$，都有 $a_{n+2}=a_{n+1}+a_{n}+1$．
【难度】
【出处】
2013年中国西部数学邀请赛试题
【标注】
【答案】
略
【解析】
证法一
设 $A$ 为 $n$ 级好集合，且 $|A|=k$，则由已知有 $\min_{x\in A}x\geqslant k$，于是 $A\subset \{k,k+1,\ldots,n\}$，因此满足 $|A|=k$ 的 $n$ 级好集合有 $C_{n-k+1}^{k}$ 个．
所以 $
a_{n}=\sum_{k=1}^{\left[\frac{n+1}{2}\right]} C_{n k+1}^{k}=C_{n}^{1}+C_{m-1}^{2}+C_{n-2}^{3}+\ldots
$
当 $n$ 为偶数时，设 $n=2m$，则
$\begin{aligned} a_{2 m+2} =&C_{2 m+2}^{2}+C_{2 m+1}^{2}+\ldots+C_{m+2}^{m+1} \\ =&\left(C_{2 m+1}^{1}+C_{2 m+1}^{0}\right)+\left(C_{2 m}^{2}+C_{2 m}^{1}\right)+\ldots+\left(C_{m+1}^{m+1}+C_{m+1}^{m}\right)\\ =&\left(C_{2 m+1}^{1}+C_{2 m}^{2}+\ldots+C_{m+1}^{m+1}\right)+\left(C_{2 m}^{1}+C_{2 m-1}^{2}+\ldots+\right.\\ & C_{m+1}^{m}+C_{2 m+1}^{0} \\ =&a_{2 m+1}+a_{2 m}+1 \end{aligned}$
当 $n$ 为奇数时，设 $n=2m-1$，则
$\begin{aligned} a_{2 m+1} =&C_{2 m+1}^{2}+C_{2 m}^{2}+\ldots+C_{m+2}^{m}+C_{m+1}^{m+1} \\ =&\left(C_{2 m}^{1}+C_{2 m}^{0}\right)+\left(C_{2 m-1}^{2}+C_{2 m-1}^{1}\right)+\ldots+\left(C_{m+1}^{m}+C_{m+1}^{m-1}\right)+C_{m}^{m}\\ =&\left(C_{2 m}^{1}+C_{2 m-1}^{2}+\ldots+C_{m+1}^{m}\right)+\left(C_{2 m-1}^{1}+C_{2 m-2}^{2}+\ldots+\right.\\ & \left.C_{m+1}^{m-1}+C_{m}^{m}\right)C_{2 m}^{0} \\ =&a_{2 m}+a_{2 m-1}+1 \end{aligned}$
综上所述，$a_{n+2}=a_{n+1}+a_{n}+1$ 对一切正整数 $n$ 都成立，
注：由组合恒等式 $\sum_{k=0}^{\left[\frac{n}{2}\right]} C_{n-k}^{k}=F_{n}$（其中 $F_n$ 为斐波那契数列的第 $n$ 项）可知，本题中的 $a_n =F_{n+1}-1$．
证法二
所有 $n+2$ 级好集合可按以下标准分为 $3$ 类：
（a）不含元素 $n+2$；
（b）含有元素 $n+2$，且不是一元集；
（c）一元集 $\{n+2\}$．
显然（c）类中的集合符合 $n+2$ 级好集合的定义．以下我们对（a），（b）两类中的好集合进行计数．
对于（a）类中的好集合 $A$，由于 $|A|\leqslant\min_{x\in A}x$ 且 $\max_{x\in A}x\leqslant n+1$，
故 $A$ 是 $n+1$ 级好集合．反之，所有 $n+1$ 级好集合也是 $n+2$ 级好集合，
因此 $(a)$ 类中的好集合个数为 $a_{n+1}$；对于（b）类中的好集合 $A$，
记 $A=\{ b_1 , b_2 , \ldots , b_k , n+2\}$，$b_1 < b_2 < \ldots < b_k < n+2$．
易知 $b_1 = \min_{x\in A}x\geqslant |A|\geqslant 2$，故可将 $A$ 对应到集合 $
A'=\left\{b_{1}-1, b_{2}-1, \ldots, b_{k}-1\right\}
$
其中 $
1 \leqslant b_{1}-1<b_{2}-1<\ldots<b_{k}-1<n+1
$
且此时 $
\left|A^{\prime}\right|=|A|-1 \leqslant b_{1}-1=\min _{x \in A^{\prime}} x
$
因此 $A'$ 是 $n$ 级好集合．反之，所有 $n$ 级好集合均可表示为形加 $A'=\{ b_1 -1,b_2 -1,\ldots,b_k -1\}$ 的形式，故所有（b）类好集合与 $n$ 级好集合全体形成一一对应，故（b）类好集合的个数为 $a_n$．
综上可知，（a），（b），（c）三类好集合的个数为 $a_{n+2}=a_{n+1}+a_{n}+1$．
证毕．
设 $A$ 为 $n$ 级好集合，且 $|A|=k$，则由已知有 $\min_{x\in A}x\geqslant k$，于是 $A\subset \{k,k+1,\ldots,n\}$，因此满足 $|A|=k$ 的 $n$ 级好集合有 $C_{n-k+1}^{k}$ 个．
所以 $
a_{n}=\sum_{k=1}^{\left[\frac{n+1}{2}\right]} C_{n k+1}^{k}=C_{n}^{1}+C_{m-1}^{2}+C_{n-2}^{3}+\ldots
$
当 $n$ 为偶数时，设 $n=2m$，则
$\begin{aligned} a_{2 m+2} =&C_{2 m+2}^{2}+C_{2 m+1}^{2}+\ldots+C_{m+2}^{m+1} \\ =&\left(C_{2 m+1}^{1}+C_{2 m+1}^{0}\right)+\left(C_{2 m}^{2}+C_{2 m}^{1}\right)+\ldots+\left(C_{m+1}^{m+1}+C_{m+1}^{m}\right)\\ =&\left(C_{2 m+1}^{1}+C_{2 m}^{2}+\ldots+C_{m+1}^{m+1}\right)+\left(C_{2 m}^{1}+C_{2 m-1}^{2}+\ldots+\right.\\ & C_{m+1}^{m}+C_{2 m+1}^{0} \\ =&a_{2 m+1}+a_{2 m}+1 \end{aligned}$
当 $n$ 为奇数时，设 $n=2m-1$，则
$\begin{aligned} a_{2 m+1} =&C_{2 m+1}^{2}+C_{2 m}^{2}+\ldots+C_{m+2}^{m}+C_{m+1}^{m+1} \\ =&\left(C_{2 m}^{1}+C_{2 m}^{0}\right)+\left(C_{2 m-1}^{2}+C_{2 m-1}^{1}\right)+\ldots+\left(C_{m+1}^{m}+C_{m+1}^{m-1}\right)+C_{m}^{m}\\ =&\left(C_{2 m}^{1}+C_{2 m-1}^{2}+\ldots+C_{m+1}^{m}\right)+\left(C_{2 m-1}^{1}+C_{2 m-2}^{2}+\ldots+\right.\\ & \left.C_{m+1}^{m-1}+C_{m}^{m}\right)C_{2 m}^{0} \\ =&a_{2 m}+a_{2 m-1}+1 \end{aligned}$
综上所述，$a_{n+2}=a_{n+1}+a_{n}+1$ 对一切正整数 $n$ 都成立，
注：由组合恒等式 $\sum_{k=0}^{\left[\frac{n}{2}\right]} C_{n-k}^{k}=F_{n}$（其中 $F_n$ 为斐波那契数列的第 $n$ 项）可知，本题中的 $a_n =F_{n+1}-1$．
证法二
所有 $n+2$ 级好集合可按以下标准分为 $3$ 类：
（a）不含元素 $n+2$；
（b）含有元素 $n+2$，且不是一元集；
（c）一元集 $\{n+2\}$．
显然（c）类中的集合符合 $n+2$ 级好集合的定义．以下我们对（a），（b）两类中的好集合进行计数．
对于（a）类中的好集合 $A$，由于 $|A|\leqslant\min_{x\in A}x$ 且 $\max_{x\in A}x\leqslant n+1$，
故 $A$ 是 $n+1$ 级好集合．反之，所有 $n+1$ 级好集合也是 $n+2$ 级好集合，
因此 $(a)$ 类中的好集合个数为 $a_{n+1}$；对于（b）类中的好集合 $A$，
记 $A=\{ b_1 , b_2 , \ldots , b_k , n+2\}$，$b_1 < b_2 < \ldots < b_k < n+2$．
易知 $b_1 = \min_{x\in A}x\geqslant |A|\geqslant 2$，故可将 $A$ 对应到集合 $
A'=\left\{b_{1}-1, b_{2}-1, \ldots, b_{k}-1\right\}
$
其中 $
1 \leqslant b_{1}-1<b_{2}-1<\ldots<b_{k}-1<n+1
$
且此时 $
\left|A^{\prime}\right|=|A|-1 \leqslant b_{1}-1=\min _{x \in A^{\prime}} x
$
因此 $A'$ 是 $n$ 级好集合．反之，所有 $n$ 级好集合均可表示为形加 $A'=\{ b_1 -1,b_2 -1,\ldots,b_k -1\}$ 的形式，故所有（b）类好集合与 $n$ 级好集合全体形成一一对应，故（b）类好集合的个数为 $a_n$．
综上可知，（a），（b），（c）三类好集合的个数为 $a_{n+2}=a_{n+1}+a_{n}+1$．
证毕．
答案
解析
备注
