Processing math: 17%

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


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

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

пред. Правка 2   1
1 года 2 месяца назад #

За \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.