Processing math: 100%

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


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

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

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

За αk обозначим количество k-элементарных n-хороших множеств. Заметим, что так как |A|minxAx, то αk=Cknk+1.

Тогда пользуясь Ck+1n+1=Ckn+Ck+1n выходит, что:

an+2=α1+α2+...=C1n+2+C2n+1+...=C0n+1+C1n+1+C1n+C2n+...=C1n+1+C2n+...+C1n+...+1=an+1+an+1.