MathDB

5

Part of 2013 China Western Mathematical Olympiad

Problems(1)

2013 China Western Mathematical Olympiad ,Problem 5

Source: China Lanzhou 18 Aug 2013

8/18/2013
A nonempty set AA is called an nn-level-good set if A⊆{1,2,3,…,n} A \subseteq \{1,2,3,\ldots,n\} and ∣A∣≤min⁡x∈Ax|A| \le \min_{x\in A} x (where ∣A∣|A| denotes the number of elements in AA and min⁡x∈Ax\min_{x\in A} x denotes the minimum of the elements in AA). Let ana_n be the number of nn-level-good sets. Prove that for all positive integers nn we have an+2=an+1+an+1a_{n+2}=a_{n+1}+a_{n}+1.
combinatorics proposedcombinatorics