Западно-Китайская математическая олимпиада, 2013 год

Непустое множество $A$ называется $n$-хорошим, если $ A \subseteq \{1,2,3,\ldots,n\}$ и $|A| \le \min_{x\in A} x$ ($\min_{x\in A} x$ обозначает наименьший элемент $A$). Пусть $a_n$ обозначает число $n$-хороших множеств. Докажите, что для всех натуральных $n$ верно равенство $a_{n+2}=a_{n+1}+a_{n}+1$.

Комментарий/решение

За $\alpha_k$ обозначим количество $k$-элементарных $n$-хороших множеств. Заметим, что так как $|A|\leq \min_{x\in A}x$, то $\alpha_k=C_{n-k+1}^k$.

Тогда пользуясь $C_{n+1}^{k+1}=C_{n}^k+C_{n}^{k+1}$ выходит, что:

$$a_{n+2}=\alpha_1+\alpha_2+...=C_{n+2}^1+C_{n+1}^2+...=C_{n+1}^0+C_{n+1}^{1}+C_{n}^1+C_{n}^2+...=C_{n+1}^1+C_{n}^2+...+C_{n}^1+...+1=a_{n+1}+a_{n}+1.$$