Западно-Китайская математическая олимпиада, 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.
посмотреть в олимпиаде
Комментарий/решение:
За \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.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.