Problem

Source: China Lanzhou 18 Aug 2013

Tags: combinatorics proposed, combinatorics



A nonempty set $A$ is called an $n$-level-good set if $ A \subseteq \{1,2,3,\ldots,n\}$ and $|A| \le \min_{x\in A} x$ (where $|A|$ denotes the number of elements in $A$ and $\min_{x\in A} x$ denotes the minimum of the elements in $A$). Let $a_n$ be the number of $n$-level-good sets. Prove that for all positive integers $n$ we have $a_{n+2}=a_{n+1}+a_{n}+1$.