Западно-Китайская олимпиада по математике 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$.